快指针和慢指针如何在链表中找到循环的第一个节点？

Question

当使用fast和slow的方法时，在一个有环的链表中。这两个指针将在一个节点处相遇。然后取两个指针中的一个指向头结点，另一个指针留下。接下来，让他们每次都迈出一步。最后，他们将在循环的第一个节点相遇。我想知道为什么。谢谢。what I mean the "first node in the loop"

Answer 1

您将通过手动解决几个示例来理解这一点：

1 -> 2 -> 3 -> 4 (suppose 4 is connected to 2)
- (fast)
+ (slow)
[start moving]

1 -> 2 -> 3 -> 4
     -
          +
1 -> 2 -> 3 -> 4
          -
     +
1 -> 2 -> 3 -> 4
               -
               +
Now the have met. Let's declare 2 pointers @ and # pointing to the head and the node where they met respectively
1 -> 2 -> 3 -> 4
@
               #
1 -> 2 -> 3 -> 4
     @
     #
This is obviously the start of the cycle.

第一个观察：如果有一个循环，慢和快会相遇。这是他们采取的步骤长度的结果。 2的每一个倍数都能被1整除。

第二个观察：在循环的情况下，慢速和快速交汇点在循环内。原因很明显，fast 不会退出循环所以他们就在那里相遇。

现在，假设从头到循环开始的距离是 A，从循环开始到快慢相遇的节点的距离是 B。可以说慢的走过了A+B遇见了快。在此期间快速旅行了多少？ 2A+2B，因为它的移动速度是原来的两倍。

现在，让我们找到另一个表示快速行进距离的公式，它可以帮助我们解决这个方程。我们可以说 fast 从头到循环的开始 A 加上从循环的开始到交汇点 B 加上从交汇点到链表的末尾，我们称之为 C，又从循环开始到集合点B。即 A + B + C + B 等于 A+2B+C，其中 C 是从交汇点到链表末尾的距离。希望在没有插图的情况下有意义。

总结到这里：

A: dist from start of the list to the start of the cycle
B: dist from start of the cycle to the meeting point of slow and fast
C: dist from meeting point to the end of the list

slow has traveled: A + B
fast has travelled: 2A + 2B (because it moves at double speed)
We can also say fast has traveled: A + B + C + B = A+2B+C

让我们将 fast 移动距离的这 2 个表达式等同起来，并希望求解 A，即从头到循环开始的距离。

A+2B+C = 2A+2B
A = C

这实际上意味着从头到循环开始的距离，即A，等于交汇点到链表末尾的距离，即C。

如果那是真的，我们可以运行 2 个指针，a 和 b，一个来自头部，一个来自交汇点。当 b 到达链表的末尾时， a 处于循环的开始。但是由于有一个循环b永远不会走到尽头。我们创建一个条件，当 b == a 时我们找到了循环的开始。这是可行的，因为最后一个节点之后的下一个节点是循环的开始。

注意我的解释：方程式并不完全准确。在长链表和非常小的循环的情况下，fast 可能会移动 B 和 C 的倍数，直到 slow 遇到它。所以，A+2B+C 变成了 A+iB+iC+B。但这并没有改变最终结果。

顺便提一句 Floyd's Hare and Turtoise algorithm 如果您想进一步阅读它。

如果还不够清楚，请提问。

快指针和慢指针如何在链表中找到循环的第一个节点？

How can fast and slow pointers find the first node of loop in a linkedlist?

algorithm

pointers

data-structures