最佳算法来测试链表是否有循环。

Question

32

什么是检测链表中是否存在循环的最佳（停机）算法？

[编辑] 分析时间和空间的渐进复杂度会更好，这样答案可以更好地进行比较。

[编辑] 最初的问题没有涉及出度> 1的节点，但有一些讨论。那个问题更多的是“检测有向图中循环的最佳算法”。

- cdleary

https://dev59.com/TnE85IYBdhLWcg3wr1ge - Pramod

可能是如何检测链表中的循环？的重复问题。 - roottraveller

12个回答

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

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

- DrPizza · Answer 1

在这种情况下，OysterD的代码将是最快的解决方案（顶点着色）。

那真的会让我惊讶。我的解决方案最多只需通过列表两次（如果最后一个节点链接到倒数第二个节点），而在常见情况下（没有循环），它只需要通过一次。没有哈希，没有内存分配等。

- Konrad Rudolph · Answer 2

在这种情况下，OysterD的代码将是最快的解决方案（顶点着色）。

那真的会让我很惊讶。我的解决方案最多只需通过列表两次（如果最后一个节点链接到倒数第二个节点），在常见情况下（没有循环）只需通过一次。没有哈希，没有内存分配等等。

是的。我注意到表述不完美，并进行了重新措辞。我仍然相信聪明的哈希可能会更快 - 仅仅是一点点。我相信你的算法是最好的解决方案。

只是为了强调我的观点：现代垃圾收集器使用顶点着色来检测依赖关系中的循环，因此有一个非常实际的用例。它们主要使用位标志来执行着色。