为什么在查找链表中的循环时要将指针增加两个，而不是3、4或5个？

Question

我看过这个问题，其中讨论了在链表中找到循环的算法。我已经阅读了Floyd's cycle-finding algorithm的解决方案，在很多地方提到我们必须采取两个指针。一个指针( slower/tortoise )每次增加1，另一个指针( faster/hare )每次增加2。当它们相等时，我们发现了循环，如果快速指针到达null，则没有循环在链表中。

现在我的问题是为什么我们要将快速指针增加2。为什么不是其他数值？是否必须增加2才能得到结果，或者我们可以通过增加X来获得结果。如果我们将快速指针增加2，是否必定会找到一个循环，还是可能需要增加3、5或X。

- GG.

---

很不幸，像你链接中的第一篇文章（弗洛伊德算法）这样的文章，是由那些并不太关心如何教别人理解算法的人编写的。我能接受该算法的有效性，但仍未找到一个良好的英文描述它为什么有效。希望我的回答能够提供这样的描述。 - Lasse V. Karlsen

@Lasse 我和你的情况一样，我知道它能工作，但不明白它是如何工作以及背后的逻辑。 - GG.

看一下Brent算法，它更好。 - starblue

@LasseVågsætherKarlsen 请查看此答案。 - AAB

Answer 1

从正确性的角度来看，没有必要使用数字2。任何步长都可以使用（当然除了1）。但是，选择步长为2最大化了效率。

为了看到这一点，让我们先看看为什么弗洛伊德算法起作用。思路是考虑序列x₀，x₁，x₂，...，x_n，... 中的元素，如果您从列表开头开始向下行走，直到到达结尾，那么您将访问该序列。如果列表不包含循环，则所有这些值都是不同的。但是，如果它包含一个循环，那么这个序列将无限重复。

这里是使弗洛伊德算法起作用的定理：

如果存在正整数j，使得对于任何正整数k，x_j=x_jk，则链表包含一个循环。

让我们证明这一点；这不难。对于“如果”情况，如果存在这样的j，则取k = 2。然后我们有对于某个正 j，x_j=x_2j且j ≠ 2j，因此列表包含一个循环。

对于另一方面，假设列表以位置s开始的长度为l的循环。让j是大于s的最小l的倍数。然后对于任何k，如果我们考虑x_j和x_jk，由于j是循环长度的倍数，我们可以将x_jk视为从列表中的位置j开始，然后进行（k-1）次j步骤形成的元素。但是每次您执行j步骤时，您都会回到列表中的起始位置，因为j是循环长度的倍数。因此，x_j=x_jk。

此证明保证了，如果您在每个迭代中都采取恒定步数，那么您确实会撞上慢指针。更确切地说，如果您在每个迭代中采取k步，则最终将找到点x_j和x_kj并检测出循环。通常人们倾向于选择k=2以最小化运行时间，因为在每个迭代中您需要采取的步骤数量最少。

我们可以按如下方式更加形式化地分析运行时间。如果列表不包含循环，则快指针将在O(n)时间内经过n步到达列表尾部。否则，在慢指针已经走了j步之后，两个指针将相遇。请记住，j是大于s的最小l倍数。如果s≤l，则j=l；否则，如果s>l，则j最多为2s，因此j的值为O(s+l)。由于l和s不能超过列表中的元素数量，这意味着j = O(n)。然而，在慢指针走了j步之后，快指针将采取k步，每次慢指针走一步，所以它将采取O(kj)步。由于j=O(n)，因此净运行时间最多为O(nk)。请注意，这表明我们采取的步数越多，算法完成所需的时间就越长（尽管成比例增加）。因此，选择k = 2可以最小化算法的总运行时间。

希望这有所帮助！

- templatetypedef

---

你的证明难道不是基于你已经知道了要找到的循环长度，这样你才可以为兔子选择适当的速度吗？虽然这会产生一个对于该循环长度总是有效的兔子，但它不能保证对于不同长度的循环也一定有效（除非你选择速度2）。 - Mike Tunnicliffe

@fd- 这个证明本身并不假设你知道循环长度；它只是说对于任何循环长度和循环起始位置，都存在某个位置j具有所需的属性。如果你考虑修改过的龟兔算法的工作原理，它会以1和k的速率开始推进两个指针。在走了j步之后，这两个指针会位于位置j和jk处，它们是重合的。为到达它，你不需要知道j是什么。这听起来合理吗？ - templatetypedef

@Nikita Rybak- 是的，这是正确的。该算法的运行时间与步长成正比，这就是为什么我们通常选择2的原因。 - templatetypedef

谁给这个回答踩了一下，你能解释一下哪里有问题吗？ - templatetypedef

解释非常妙。盯着“让j是大于s的最小倍数”看了一分钟后，我恍然大悟：这意味着如果你从起点走j步，你就在循环内（因为j > s），如果你再从那里走j步，你会回到同一个地方（因为j是l的倍数）。所以任何j步数的倍数也都成立。虽然我们不知道j是多少，但我们知道它必须存在，而且每次移动时我们有效地问“这是j吗？”，所以我们不会错过它。 - j_random_hacker

Answer 2

假设不包含循环的列表长度为 s ，循环长度为，fast_pointer_speed与slow_pointer_speed的比率为。

让两个指针在距离循环开始处相遇。

因此，慢指针行驶的距离= s + j 。快指针行驶的距离= s + j + m * t （其中是快指针完成循环的次数）。但是，快指针还会行驶距离 *（ s + j ）（慢指针的距离乘以倍）。

因此，我们得到 *（ s + j ）= s + j + m * t 。 s + j =（m / k-1）t 。

因此，从上述方程中，慢指针行驶的距离是循环长度的整数倍。

为了达到最大效率，（m / k-1）= 1 （慢指针不应超过一次循环）。

因此， m = k-1 => k = m + 1 由于是快指针完成循环的次数，所以≥1。 为了实现最大效率， m = 1 。

因此 k = 2 。

如果我们取一个值> 2，则两个指针需要行驶更长的距离。

希望以上解释有所帮助。

- Sumit Das

---

@Sumit：如果你计算指针速度的比值，较慢的指针是否有可能已经遍历了循环多次，因此较慢指针所走过的距离可能不仅仅是 s+j。假设较慢的指针每次移动 2 步，而较快的指针每次移动 5 步。我有什么遗漏吗？ - ultimate cause

是的。没错。如果你取2的比率，那么较短的指针不需要遍历循环超过一次，因此是最优的。这就是我试图证明的。正如你所指出的，其他比率都不是最优的，较短的指针可能会遍历循环超过一次。 - Sumit Das

你能解释一下为什么在这个方程式中：s + j = (m / k-1)t，(m/k-1) 必须是整数吗？ - gaurav jain

谢谢，这终于为我澄清了算法。 - septerr

所以，慢指针走过的距离 = s + j。你不是已经假设慢指针没有形成任何循环了吗？ - rohit_r

Answer 3

考虑一个大小为L的循环，意味着在第k个元素上出现了循环：x_k -> x_k+1 -> ... -> x_k+L-1 -> x_k。假设一个指针以速率r₁=1运行，另一个以速率r₂运行。当第一个指针到达x_k时，第二个指针将已经在循环中某个元素x_k+s处（其中0 <= s < L）。在m次进一步指针增量之后，第一个指针在x_{k+(m mod L)}处，第二个指针在x_{k+((m*r2+s) mod L)}处。因此，两个指针碰撞的条件可以表述为存在一个满足同余的m：

m = m*r₂ + s (mod L)

这可以通过以下步骤简化：

m(1-r₂) = s (mod L)

m(L+1-r₂) = s (mod L)

这是线性同余式的形式。如果s能被gcd(L+1-r₂,L)整除，则它有解m。如果gcd(L+1-r₂,L)=1，则肯定会这样。如果r₂=2，则gcd(L+1-r₂,L)=gcd(L-1,L)=1，始终存在一个解m。

因此，r₂=2具有良好的性质，即对于任何循环大小L，它都满足gcd(L+1-r₂,L)=1，因此即使两个指针从不同位置开始，也保证它们最终会相撞。其他值的r₂没有这个性质。

- user782220

---

非常有趣的是，双倍速的兔子具有这种额外的“随处起跑”的特性。我需要更好地理解模算术（除了“如果s可被gcd（L+1-r2，L）整除，则它有一个解m”之外，我都理解了）。 - j_random_hacker

Answer 4

这里有一个直观的非数学方法来理解这个问题：

如果快指针跑到链表末尾，显然没有循环。

我们只需要让指针进入循环中即可，不用关心它们在循环之前的位置。当慢指针最终到达循环时，快指针的位置无关紧要。

一旦它们都进入了循环，它们就在循环中转圈，但在不同的位置。想象一下，如果它们每次都向前移动一个位置，那么它们就会在循环中转圈，但是保持相同的距离。换句话说，它们做着相同的循环，但是相位不同。现在通过将快指针每次向前移动两个位置，它们就会改变彼此的相位。每次缩小一个单位的距离。快指针将追上慢指针，我们就可以检测到循环。

为了证明这是正确的，证明它们会相遇并且快指针不会以某种方式超越并跳过慢指针，只需手动模拟以下情况：当快指针落后于慢指针三步时，然后模拟快指针落后于慢指针两步时，再然后快指针只落后于慢指针一步时。在每种情况下，它们都会在同一个节点相遇。任何更大的距离最终将成为三个单位、两个单位或一个单位的距离。

- Peter Theobald

---

虽然这个解释可以用来说明循环检测，但它只回答了“为什么是2？”而没有回答3、4、5等的问题。因此，虽然这不是一个坏答案，但我认为它实际上并没有回答这个问题。 - Quinn Mortimer

Answer 5

如果快指针移动了3步，慢指针移动了1步，在包含偶数个节点的循环中，不能保证两个指针都会相遇。然而，如果慢指针移动了2步，则相遇是有保证的。

一般来说，如果兔子每次移动H步，乌龟每次移动T步，则当且仅当H = T + 1时，你可以保证它们会在一个循环中相遇。 考虑兔子相对于乌龟的移动。

• 相对于乌龟，兔子每次移动H - T个节点。

• 给定长度为N =(H - T) * k的循环，其中k是任意正整数，如果兔子跳过了每个H - T - 1个节点（再次相对于乌龟），并且乌龟在这些节点中的任何一个节点上，它们就不可能相遇。

• 唯一保证相遇的可能性是H - T - 1 = 0。

因此，只要慢指针增加了x - 1，就可以增加快指针x的移动步数。

- John Bupit

Answer 6

如果有一个循环（n个节点），那么一旦指针进入循环，它将永远停留在那里；因此我们可以向前移动时间，直到两个指针都在循环中。从这里开始，指针可以用模n的整数表示，其初始值为a和b。它们在t步后相遇的条件是

a+t≡b+2t mod n

它的解决方案是t=a−b mod n。

只要速度之间的差异与n没有共同的质因子，这将起作用。

参考资料 https://math.stackexchange.com/questions/412876/proof-of-the-2-pointer-method-for-finding-a-linked-list-loop 速度上的唯一限制是它们的差异应该与循环长度互质。

- Peter

Answer 7

理论上，将循环（循环）视为公园（圆形，矩形等），第一个人X的移动速度较慢，而第二个人Y的移动速度比X快。现在，不管Y以2倍还是3,4,5倍的速度移动，都会有一种情况，在某一点相遇。

- var.exe

Answer 8

选择数字2的原因是，假设慢指针移动1个单位，快指针移动2个单位，循环有5个元素。

现在为了让慢指针和快指针相遇，必须存在1、2和5的最小公倍数（LCM），它们在那里相遇。在这种情况下，它是10。

如果您模拟慢指针和快指针，您会发现慢指针和快指针在循环中的元素数为2倍时相遇。当您进行2次循环时，您将在完全相同的起始点相遇。 在非循环的情况下，它变成了1、2和无限大的LCM，所以它们永远不会相遇。

- Bhargav Reddy

Answer 9

假设我们使用两个引用Rp和Rq，它们在每次迭代中分别走p步和q步；其中p> q。在Floyd算法中，p=2，q=1。

我们知道，在某些迭代后，Rp和Rq都将在循环的某些元素处。然后，假设Rp比Rq超前x个步骤。也就是说，从Rq的元素开始，我们可以走x步到达Rp的元素。

假设，循环有n个元素。在t次进一步迭代后，Rp将比Rq超前(x+(p-q)*t)个步骤。因此，只有当：

• n可以被(x + (p-q)*t)整除时，它们才能在t次迭代后相遇

这可以写成：

• (p−q)*t ≡ (−x) (mod n)

由于模算术的缘故，仅当GCD(p−q, n)| x时，才可能发生这种情况。

但我们不知道x。虽然，如果GCD为1，它将整除任何x。为了使GCD为1：

• 如果不知道n的值，选择任意p和q，使得(p-q)=1。Floyd算法确实满足p-q=2-1=1。
• 如果已知n的值，选择任意p和q，使得(p-q)与n互质。

更新：稍后进行了进一步分析后，我意识到任何不相等的正整数p和q都会在一些迭代后使两个引用相遇。尽管1和2的值似乎需要更少的总步数。

- Nitin Verma

Answer 10

如果链表有一个循环，那么增量为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。

希望我表达清楚了。

- ajayg

---

即使循环长度为L，将快指针增加L+1也是可以的。它每次都会停在同一个位置，但这不是问题，因为慢指针会追上它。 - j_random_hacker

@j_random_hacker .... 慢指针怎么可能追上快指针？两者之间的差距将始终保持不变...因为它们都像增加1一样。 - ajayg

忍不住要评论一下这个老帖子 :) 它们都像时钟面上的秒针和分针一样相遇。 - ivymike