我已经看了一下关于在链表中查找循环的算法的问题。我读过Floyd 的寻环算法解决方案，在很多地方都提到我们必须采用两个指针。一个指针（slow/tortoise）增加 1，另一个指针（faster/hare）增加 2。当它们相等时，我们找到循环，如果更快的指针达到 null，则链表中没有循环。
现在我的问题是为什么我们将更快的指针增加 2。为什么不做别的？增加 2 是必要的，或者我们可以将其增加 X 以获得结果。如果我们将更快的指针增加 2，我们是否有必要找到一个循环，或者可能存在我们需要增加 3 或 5 或 x 的情况。
从正确性的角度来看，没有理由需要使用第二个。步长的任何选择都可以（当然，除了一个）。但是，选择大小为 2 的步长可以最大限度地提高效率。
为了看到这一点，让我们先来看看为什么弗洛伊德的算法会起作用。这个想法是考虑链表元素的序列 x 0 , x 1 , x 2 , ..., x n , ... 如果您从链表的开头开始访问这些元素，然后继续走下去，直到你到达终点。如果列表不包含循环，则所有这些值都是不同的。但是，如果它确实包含一个循环，那么这个序列将无休止地重复。
这是使弗洛伊德算法起作用的定理：
当且仅当存在一个正整数 j 使得对于任何正整数 k，x j = x jk时，链表才包含一个循环。
让我们证明这一点；这并不难。对于“如果”的情况，如果存在这样的 j，则选择 k = 2。那么对于某些正数 j，x j = x 2j和 j ≠ 2j，因此列表包含一个循环。
对于另一个方向，假设列表包含从位置 s 开始的长度为 l 的循环。令 j 是 l 大于 s 的最小倍数。那么对于任意k，如果我们考虑x j和x jk，由于j 是循环长度的倍数，我们可以认为x jk是从列表中的位置j 开始，然后走j 步k-1 形成的元素次。但是每次你走 j 步，你就会回到你在列表中开始的地方，因为 j 是循环长度的倍数。因此，x j = x jk。
这个证明向您保证，如果您在每次迭代中采取任何恒定数量的步数，您确实会碰到慢速指针。更准确地说，如果您在每次迭代中采取 k 步，那么您最终会找到点 x j和 x kj并检测到循环。直觉上，人们倾向于选择 k = 2 来最小化运行时间，因为您在每次迭代中采取的步数最少。
我们可以更正式地分析运行时如下。如果列表不包含循环，则快速指针将在 n 步后到达列表末尾 O(n) 时间，其中 n 是列表中元素的数量。否则，两个指针会在慢速指针经过 j 步后相遇。请记住，j 是 l 大于 s 的最小倍数。如果 s ≤ l，则 j = l；否则，如果 s > l，则 j 最多为 2s，因此 j 的值为 O(s + l)。由于 l 和 s 不能大于列表中元素的数量，这意味着 j = O(n)。然而，在慢速指针已经走了 j 步之后，对于慢速指针所走的每 j 步，快指针将走 k 步，因此它将走 O(kj) 步。由于 j = O(n)，净运行时间最多为 O(nk)。请注意，这表示我们使用快速指针执行的步骤越多，算法完成所需的时间就越长（尽管只是成比例地如此）。因此，选择 k = 2 可以最小化算法的整体运行时间。
希望这可以帮助！
让我们假设不包含循环的列表的长度是，s循环的长度是t和的比率fast_pointer_speed是。slow_pointer_speedk
j让两个指针在距循环起点一定距离处相遇。
因此，慢速指针移动的距离 = s + j。快速指针行进的距离 = s + j + m * t（其中m是快速指针完成循环的次数）。但是，快速指针也会移动一段距离k * (s + j) （k乘以慢速指针的距离）。
因此，我们得到k * (s + j) = s + j + m * t.
s + j = (m / k-1)t.
因此，从上面的等式中，慢指针行进的长度是循环长度的整数倍。
为了获得最大(m / k-1) = 1的效率，（慢速指针不应该超过一次循环。）
所以 ，m = k - 1 => k = m + 1
因为m是快速指针完成循环的次数，m >= 1. 为了获得最大效率，m = 1.
因此k = 2.
如果我们取 的值k > 2，则两个指针必须行进的距离更大。
希望以上解释有所帮助。
考虑一个大小为 L 的循环，这意味着第 k 个元素是循环所在的位置： x k -> x k+1 -> ... -> x k+L-1 -> x k。假设一个指针以 r 1 =1的速率运行，另一个以 r 2的速率运行。当第一个指针到达 x k时，第二个指针将已经在循环中的某个元素 x k+s处，其中 0 <= s < L。在 m 进一步增加指针之后，第一个指针位于 x k+(m mod L)并且第二个指针位于 x k+((m*r 2 +s) mod L)。因此两个指针碰撞的条件可以表述为存在满足同余的m
m = m*r 2 + s (mod L)
这可以通过以下步骤来简化
m(1-r 2 ) = s (mod L)
m(L+1-r 2 ) = s (mod L)
这是线性同余的形式。如果 s 能被 gcd(L+1-r 2 ,L)整除，则它有一个解 m 。如果gcd(L+1-r 2 ,L)=1，情况肯定会如此。如果 r 2 =2 则 gcd(L+1-r 2 ,L)=gcd(L-1,L)=1 并且总是存在解 m。
因此，r 2 =2 具有良好的性质，即对于任何循环大小 L，它都满足 gcd(L+1-r 2 ,L)=1，从而保证即使两个指针从不同的位置开始，指针最终也会发生冲突。r 2的其他值不具有此属性。
如果快速指针移动3步长而慢速指针移动步1长，则不能保证两个指针在包含偶数个节点的循环中相遇。但是，如果慢速指针2按步移动，则可以保证会面。
一般来说，如果兔子H按步移动，而乌龟T按步移动，则可以保证您在一个循环中相遇 iff H = T + 1。
考虑兔子相对于乌龟移动。
H - T每次迭代的节点数。给定一个长度为 的循环N =(H - T) * k，其中k是任何正整数，兔子会跳过每个H - T - 1节点（同样，相对于乌龟而言），如果乌龟在这些节点中的任何一个节点中，它们就不可能相遇。
保证会面的唯一可能性是何时H - T - 1 = 0。
因此，x只要将慢速指针增加 ，就允许将快速指针增加x - 1。
这是一种直观的非数学方式来理解这一点：
如果快速指针超出链表的末尾，显然没有循环。
忽略指针在列表的初始非循环部分中的初始部分，我们只需要将它们放入循环中。当慢速指针最终到达循环时，快指针在循环中的哪个位置并不重要。
一旦他们都在循环中，他们就会在循环中循环，但在不同的点。想象一下，如果他们每次都移动一个。然后他们将在循环中转圈，但保持相同的距离。换句话说，制作相同的循环但异相。现在通过将快速指针每一步移动两步，它们就可以相互改变相位；每走一步就将他们之间的距离缩短一个。快速指针将赶上慢速指针，我们可以检测到循环。
为了证明这是真的，它们会相遇，并且快速指针不会以某种方式超越并跳过慢速指针，只需手动模拟快速指针落后慢速指针三步时会发生什么，然后模拟快速指针会发生什么比慢速指针落后两步，那么当快速指针仅比慢速指针落后一步时。在每种情况下，它们都在同一个节点相遇。任何更大的距离最终都会变成三、二或一的距离。
如果有一个循环（n 个节点），那么一旦指针进入循环，它将永远保持在那里；所以我们可以及时向前移动，直到两个指针都在循环中。从这里开始，指针可以用具有初始值 a 和 b 的整数模 n 表示。他们在 t 步后满足的条件是
a+t≡b+2t mod n 有解 t=a−b mod n。
只要速度之间的差异与 n 不共享主要因素，这将起作用。
对速度的唯一限制是它们的差异应该与循环的长度互质。
假设我们使用两个引用 Rp 和 Rq，它们在每次迭代中采取 p 和 q 步；p > q。在弗洛伊德算法中，p = 2，q = 1。
我们知道，在某些迭代之后，Rp 和 Rq 都将位于循环的某些元素处。然后，假设 Rp 比 Rq 领先 x 步。也就是说，从 Rq 的元素开始，我们可以走 x 步到达 Rp 的元素。
比如说，循环有 n 个元素。在 t 次进一步迭代之后，Rp 将领先于 Rq (x + (pq)*t) 步。因此，只有在以下情况下，它们才能在 t 次迭代后相遇：
可以写成：
由于模运算，这只有在以下情况下才有可能： GCD(p−q, n) | X。
但我们不知道 x。但是，如果 GCD 为 1，它将除以任何 x。要将 GCD 设为 1：
更新：在稍后的进一步分析中，我意识到任何不相等的正整数p都会q在一些迭代后使两个引用相遇。不过，1 和 2 的值似乎需要较少的总步进数。
从理论上讲，将循环（循环）视为公园（圆形，矩形等），第一人称 X 移动缓慢，第二人称 Y 移动速度比 X 快。现在，如果人 Y 以 2 的速度移动并不重要X 的倍数或 3,4,5... 倍。当他们在某一点相遇时，总会有一个案例。
如果链表有一个循环，那么增量为 2 的快速指针会比增量为 3 或 4 或更多的指针工作得更好，因为它确保一旦我们进入循环内，指针肯定会发生冲突并且不会超车。
例如，如果我们以 3 为增量并在循环内假设
fast pointer --> i
slow --> i+1
the next iteration
fast pointer --> i+3
slow --> i+2
而这种情况永远不会以 2 的增量发生。
此外，如果您真的很不走运，那么您最终可能会遇到循环长度为L并且您将快速指针增加L+1. 然后你会被无限卡住，因为移动快慢指针的差异总是L。
我希望我说清楚了。