弗洛伊德在链表中查找循环的算法，如何证明它总是有效

Question

我理解弗洛伊德周期检测算法的概念。它的结论是，如果的行进速度是野兔的两倍，并且如果在循环中领先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） 步骤之后，两个指针将相遇。

Answer 2

只要考虑一下：在n移动之后，您可以确定两个指针都将在循环中，或者其中一些指针已经结束。在接下来的n移动中，您可以确定 A 和 B 会相遇，并且由于周期的大小为 <= n，并且每一步它们之间的差异都会减小 1。

Answer 3

当然，

它适用于一个小循环。考虑两个节点的循环。那是：

A => B => C => B

所以龟兔从A开始。下表显示了发生的情况：

Tortoise  Hare
   A       A
   C       B
   C       C

当只有两个节点时，总是在它开始的地方结束。因此，基本上会保持静止，而野兔每次移动一个节点并最终追上。

顺便说一下，当你有一个只有一个节点的循环时，也会发生同样的事情。也就是说，当节点循环回自身时。

亨利的回答给出了数学证明。