linked-list - 如何判断链表是否包含循环？

Question

这个问题在这里已经有了答案:




11 年前关闭。

Possible Duplicates:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

在准备求职面试的过程中，我遇到了以下问题:

如何使用 O(1) 的额外空间复杂度来确定(任何类型的)链表是否包含循环？您不能假设循环从第一个节点开始(当然，循环不必包含所有节点)。

我找不到答案，虽然我觉得这很简单......

Answer 1

简单。维护两个指向列表的指针。在每一步，一个指针前移一个链接，另一个指针前移两个链接。测试它们是否指向同一个元素。如果是这样，你有一个循环。如果没有，请重复直到找到一个循环或到达列表的末尾。