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

Question

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

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

如果节点 A 是函数的输入，那么它应该返回 C。

因为我不知道如何称呼 C，所以我使用了术语 loop-node C，如问题中所示。虽然 O(n²) 项看起来很明显，但是否有一种方法可以找到复杂度较低的循环节点？

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

Answer 1

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

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

1.继续递增两个指针直到它们匹配。所以在上面的例子中我们会有这些步骤

Slow Pointer: A B C D E
Fast Pointer: A C E C E

所以我们在 E 处停止，这表明存在循环。现在我们需要找到循环节点。

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

Pointer From the Beginning: A B C New Pointer: E F C

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

更新:对于这种方法的数学证明，请引用这个精彩的问题并查看@Jim Lewis 的回答以及答案下方的所有评论。 Explain how finding cycle start node in cycle linked list work?