<分区>
Possible Duplicate:
How to determine if a linked list has a cycle using only two memory locations.
你好，我在一次采访中被问到如何仅使用两个指针找到链接列表中存在的循环。
我做了以下事情:
1) 每次都找到链表的中心
2) 通过在最后迭代这两个指针将指向同一个节点，如果不指向同一个节点并找到一个 null，则链表中没有循环。
有什么有效的方法可以做到这一点...？
提前致谢
标签 c++ c loops linked-list
<分区>
Possible Duplicate:
How to determine if a linked list has a cycle using only two memory locations.
你好，我在一次采访中被问到如何仅使用两个指针找到链接列表中存在的循环。
我做了以下事情:
1) 每次都找到链表的中心
2) 通过在最后迭代这两个指针将指向同一个节点，如果不指向同一个节点并找到一个 null，则链表中没有循环。
有什么有效的方法可以做到这一点...？
提前致谢
最佳答案
我认为您正在寻找 Floyd's cycle detection algorithm ，又称“龟兔赛跑算法”。这个想法是将一个指针(“乌龟”)设置为 列表中的第一个节点，以及指向下一项的另一个指针(“野兔”)。然后在 每走一步，“龟”指针前进一个位置，“兔子”指针前进两步。每次迭代后，检查指针以查看它们是否指向 同一个节点。如果发生这种情况，则该节点必须是循环的一部分。
为了找到循环的开始，将两个指针之一重新定位到 列表的开头，而另一个留在其当前位置。然后两个指针 是先进的，这一次对两个指针每次迭代一步，直到他们再次相遇。这个(第二个)交汇点是循环中的第一个节点。
关于c++ - 如何使用两个指针查找链表中是否存在循环？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3385680/