java - 如何找到带有循环的链表的循环节点？

Question

这个问题与查找 2 个链表的交集有点不同。

考虑一个带循环的链表：A - B - C - D - E - F - C。

如果 nodeA是函数的输入，那么它应该返回C.

由于我不知道该调用什么C，因此我使用了C问题中所见的术语循环节点。虽然 O(n ² ) 项看起来很明显，但有没有办法找到复杂度较低的循环节点？

不允许使用 O(n) 的哈希表/额外空间。

Answer 1

有一种使用两个指针的简单方法。第一个指针以慢速指针的速度递增一秒，第二个指针递增一倍。

因此，在您的情况下，链表实际上A->B->C->D->E->F->C意味着 F 再次指向 C.So 方法如下所示

1.继续增加两者pointers直到它们匹配。所以在上述情况下，我们将有这些步骤

慢指针：ABCDE
快指针：ACECE

所以我们停在E，这表明有一个循环。现在我们需要找到循环节点。

现在从 E 将慢速指针移动到链表的开头，并创建一个指向 E 并递增 1 的新指针。这两个指针相遇的点实际上是循环节点。所以在我们的例子中

从头开始指针：ABC 新指针：EFC

因此，正如您所见，他们在 C 处相遇，我们完成了在链表中找到循环节点的工作。

更新： 对于这种方法的数学证明，请参考这个精彩的问题并查看@Jim Lewis 的答案以及答案下方的所有评论。解释如何在循环链表中查找循环起始节点？

Answer 2

Floyd 的寻环算法是最简单的一种，通常是“标准答案”，因为这是每个人在大学里都学过的（也许是因为它简单、优雅且富有洞察力）。

还经常声称运行时不可改进，但事实并非如此 - 大哦可能不可改进，但这只会告诉我们一些关于最坏情况下的渐近行为的信息。Brent 的算法在实践中更快，同时仍然使用恒定的空间。还有更多的算法，例如 Gosper 的循环检测或 Sedgewick、Szymanski 和 Yao 的算法或k-stacks 算法，它们都使用一定的（低，但在理论上不是恒定的）空间量。实际上，对于链表的任何实际实现，空间量仍然是恒定的，因为您的指针将是固定大小的。例如，对于 32 位指针，Gosper 的循环检测将使用 33 个字的空间（可能还有几个额外的字，这取决于您要计算的内容）。

Floyd 的算法很好，但不一定是 The Answer ^(tm)。需要做出选择和权衡。