algorithm - 为什么循环中的交汇点与链表的开始步数相同？

Question

有一个明显的标准方法来查找链表是否有循环，然后返回循环开始处的节点，这是具有慢/快指针的 floy 算法。
除了一件事，代码和逻辑都很清楚。
该方法基于以下假设:指针将遇到的循环中的节点与从列表头部到循环开始的步数完全相同。 那部分是我不明白的。
因此，如果 Slow 和 Fast 都从列表的头部开始，当 Slow 执行 k 步并到达循环开始时，Fast 将执行 2k 步并有效地进入循环 k 步。
如此快比慢速领先 k 步，在慢速之后(在循环开始时)N - k，其中 N 是循环大小。
由于在每一步快速接近慢速并且快速落后于慢速 N-k 个节点，快速将在 N-k 步达到慢速。
此时，slow 将执行 N - k 步，并将在节点 N - k 中。
Fast 将完成 2(N - k) 步，并将位于节点 2N - 2k + k = 2N - k(因为 fast 位于节点 k)。
因为这是一个循环 2N - k = N - k 因此它们在节点 N - k 处相遇。
但是为什么 N - k 个节点从循环的开始是第 k 步？
我在这里误解了什么？

Answer 1

这是你所缺少的。

每当两个指针都在循环中并且快指针是前面循环长度的倍数时，快指针已经绕过慢指针整数倍并且它们在同一个位置。如果您继续，它们将分开并再次绕圈。然后再次。又一次。

算法有效的全部原因是这种重叠行为。

他们第一次见面，可能是周期长度的严格倍数。例如，如果您有一个由 24 个节点组成的链，进入一个长度为 7 的循环，那么它们将在 28 步后首先相遇。

编辑 我是在解释循环检测是如何工作的，而不是头部检测是如何工作的。这是对此的另一种解释。换句话说。

假设我们有一个 i 节点链导致一个长度为 j 的循环。我们最初运行快+慢指针，它们相遇了。为了满足，快的必须比慢的循环多走一些整数倍。所以他们在 k*j 步后相遇。

此时慢指针总共走了 k*j 步，其中 i 步进入了循环，所以它走了 k*j-i 在循环内执行。

现在我们把快指针放在开始位置，并以同样的速度前进。在另一个 i 步中，开始处的指针已到达循环。与此同时，慢速指针之前在循环内走了 k*j-i 步，现在又走了 i 步 k*j 步在循环内部。由于k*j是循环长度的倍数，所以也回到起点，再次相遇。