如何确定链表中是否包含循环？

Question

6

可能的重复问题:
查找链表中是否有循环，不使用两个指针
 如何仅使用两个内存位置确定链表是否具有循环。
测试链表是否具有循环的最佳算法

在为工作面试做准备时，我遇到了以下问题：

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

我找不到答案，尽管我觉得它很简单...

- ET.

我自己在面试中错过了这个确切的问题。我只能提供O（n）的内存和时间解决方案。 - Thanatos

1

我在计算机科学课上学过这个，但我认为这不是一个特别好的问题，因为它“只有在你已经知道的情况下才显而易见”。 - Brendan Long

Danny 发布了一个很好的回答--如果你想学习更多关于它的搜索术语，可以尝试搜索“Floyd 循环检测算法”或“龟兔算法”。 - Jim Lewis

3个回答

1

可能与检查图是否为树的技术相同（树不允许有循环），请参见this this question。建议使用拓扑排序或深度优先搜索。

- zdav

-1

上周在实际的代码中我遇到了这个完全相同的问题。

我所做的只是保留一个指针（链接）指向第一个元素。然后当我遍历列表时，如果我再次遇到那个指针，我就知道有一个循环。

- T.E.D.

1

请查看最佳答案的评论，了解为什么这个方法无法捕捉到所有的循环，并且为什么有更好的解决方案。 - T.E.D.

循环不一定从第一个元素开始。 - Nicolas Barbulesco

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dty · Accepted Answer

简单。将两个指针定位在链表中。每一步，一个指针向前移动一个链接，另一个指针向前移动两个链接。测试它们是否指向同一个元素。如果是，则存在一个循环。如果不是，则重复此过程直到找到循环或达到链表的末尾。