algorithm - 用于在链表中查找循环的 Floyd 算法，如何证明它总是有效

Question

我了解 Floyd 循环检测算法的概念。它得出的结论是，如果乌龟的行进速度是兔子的两倍，并且如果乌龟在一个循环中领先 k 米，则乌龟和兔子将在循环前 k 米处相遇。

在单链表的情况下，指针 A 的移动速度是指针 B 的两倍。这意味着如果指针 B 需要 k 步才能到达循环的入口点(我们还不知道它在哪里), 指针 A 在循环内已经有 k 个节点的先行者。因此，两个指针会在循环入口点之前遇到k个节点。因此，如果我们将指针 B 移回头指针并将指针 A 保持在交汇点(现在两个指针距离入口点 k 个节点)，并且以相同的速度移动两者，它们将在入口点相遇循环。

如何证明该算法在以下边界情况下有效？

1. 最后一个节点循环回到头部的链表。在这种情况下，领先起点值 k 是多少？
2. 超长链表，1000个节点，最后有一个小环，3个节点。指针A将领先1000，这意味着当指针B到达循环入口点时，A已经循环了很多次。
3. 如果有1个节点的循环怎么办？

这不是作业。一位面试官告诉我，如果我有一个小循环，这个算法将无法工作。他没有解释原因。

Answer 1

很明显，如果有一个，两个指针最终都会到达循环。假设循环的长度为 N。我们可以计算循环中的位置模 N。

现在假设指针 A 位于位置 a，指针 B 位于位置 b。在 s 步之后，A 将位于 a+2s mod N，B 将位于 b+s mod N。为了使两个指针相交，我们必须有

a+2s = b+s (mod N)
a+s = b (mod N)
s = b - a (mod N)

所以在 b - a (mod N) 步之后，两个指针会相遇。