问，“如何检测链表是循环链表”
如果长度为N的链表如何检测
如果允许做标记，如何检测，
最难的 如果链表的循环在任意位置，任意长度，如何检测是循环链表。
恩，就是这道题，

Use two pointers, one pointer one-step-at-a-time, one pointer two-steps-at-a-time. Check they are equal or not each time.

If cycle exists, they will meet eventually.

All your problems are solved this way!

This is a real interview question, my friend got this one from AA.

设定一标记一结点，从这结点开始，只要重新遍历到该结点则表示有循环。

[size=4]Wrong!!![/size]

Since this might 标记 on the point before cycle happens.

Just think the letter b, circle does exist, but if you mark at the beginning will be garanteed to fail.

[[italic] 本帖最后由 ranchgirl 于 2007-12-10 10:34 编辑 [/italic]]

哦,长见识了啊

"如何检测链表是循环链表”

The question is how to examine  the link list  make a circle,not  to judge the link list have a circle.

To  nuciewth:

Did you even read the entire question?????

最难的 如果链表的循环在任意位置，任意长度，如何检测是循环链表。

那就不叫循环链表.
我所学到的循环链表就是头尾相接,组成一个圈.而不是一个带环的链表.

如果真的要检测,只要设定已经被访问标记即可.(必要时可以修改data域)