algorithm - 希望了解在单链表中找到循环开始的算法

Question

这个问题有一个非常优雅的解决方案，但我不明白最大的部分 - 为什么在将 S 移回列表的开头之后，S 和 F 与循环开始的距离相同？他做了一些数学来“证明”它，但这对我来说不太有意义。任何有助于更好地理解这一点的帮助将不胜感激。谢谢！

Answer 1

为了解决这个问题，我们假设有一个n节点循环开始m节点之后的起点，并且我们使用慢速指针 S（每一步一个节点）和一个快速指针 F（每一步两个节点）来遍历它。为简洁起见，我们假设m < n，但这并不重要（只需做一些模运算）。

关键是要意识到 S 和 F 将在节点重叠n - m。文章中完成的数学运算确实有点难以理解，并且似乎没有推广到奇怪的情况n。不确定这会容易得多，但我会尝试。

假设 S 从循环的开头开始，F 从循环开始的k节点开始，我们开始遍历循环。在时间步x，S 将是循环开始之后的节点x，F 将是循环2x + k开始之后的节点。当然，在 F 越过循环起点之前，F 不会超过 S，此时我们可以等效地将其描述为起点之后的(2x + k) - n = 2x - (n - k)节点。

我们现在问，“S 和 F 会在哪一步x重叠？” 这只是当 S 的位置等于 F 的位置时，所以x = 2x - (n - k)，或（使用一些简单的代数），x = n - k。因此，两个指针都将是n - k循环开始之后的节点。

回到最初的问题（两个指针都从链表的头部开始），当 S 到达起点时（以m步为单位），F 将经过多2m步，因此将成为m循环起点之后的节点（2m - m = m）。替换k为m上面，我们看到当我们继续时，当指针 F（和 S）是n - m超过循环开始的节点时，节点将重叠。因此，如果我们将 S 移回开头，则 F 和 S 都将采取m措施回到循环的开头。

让我知道这是否有帮助。

Answer 2

1. 取 2 个指针（f 和 s）。
2. 从链接列表头开始两个指针。使 f(faster) 以 s(slower) 的速度遍历两倍，即 f 将跳转两次，s 将跳转一次。
3. 检查他们是否会见面。
4. 如果他们相遇，则使 s 指向链接列表的开头并且不更改 f 的值（因为 f 现在指向他们的会议节点）
5. 现在使两个指针速度相等，并使它们仅移动一个节点。
6. 他们相遇的点将是循环的开始。（要做到这一点，只需画一张图或理解上面的帖子。

让我知道你是否明白这一点。将很乐意为您提供帮助。