如何在循环链表中找到环的起点节点？

Question

如何在循环链表中找到环的起点节点？

algorithmlinked-listcyclefloyd-cycle-finding

201

我知道乌龟和兔子相遇的地方标志着一个循环的存在，但是当我们将乌龟移动到链表的开头并保持兔子在相遇的地方，然后两个指针都每次向前移动一步时，它们如何会聚到循环的起点呢？

- Passionate programmer

另一个解释：https://marcin-chwedczuk.github.io/find-cycle-start-in-singly-linked-list - csharpfolk

我想知道如果使用Brent算法，是否有人能够轻松找到循环的起点。 - gnasher729

23个回答

145

请参考这张图片：

慢指针相遇前行驶的距离 = x + y

快指针相遇前行驶的距离 = (x + y + z) + y = x + 2y + z

由于快指针的速度是慢指针的两倍，并且在到达相遇点时时间是恒定的。

因此，通过简单的速度、时间和距离关系公式，我们得出： 2(x+y)= x+2y+z => x+2y+z = 2x+2y => x=z

因此，将慢指针移动到链表的开头，并让慢指针和快指针每次移动一个节点，它们需要覆盖相同的距离。

它们将到达链表中循环开始的位置。

- Atul Yadav

19

这并未考虑快指针在慢指针进入循环之前已经绕循环走了n次的情况。用l表示循环长度。快指针相遇前行驶的距离 = (x + y + z) + y = x + 2y + nl + z。因此可以得到关系式：x = nl+z。 - Jingguo Yao

1

@JingguoYao：这是那个案例的解释。 - displayName

4

这个图过于简略。在慢指针到达快指针之前，快指针可以在循环中移动多次。 - Warren MacEvoy

1

@Warren MacEvoy：这个图表很简单，这是一件好事。它有助于理解基本情况。下一个情况在这里。那种情况同样容易理解。 - displayName

@Warren MacEvoy “快指针在慢指针到达之前可以多次通过循环移动。” 不是快指针和慢指针在同一位置相遇吗，而不是反过来？可能这只是角度问题。 - uzluisf

95

这是弗洛伊德的循环检测算法。你问的是算法的第二个阶段——一旦找到一个在循环中的节点，如何找到循环的起点？

在Floyd算法的第一部分，兔子每走一步，乌龟就走两步。如果乌龟和兔子相遇，则存在一个循环，并且相遇点是循环的一部分，但不一定是循环中的第一个节点。

当乌龟和兔子相遇时，我们已经找到了最小的i（乌龟走过的步数），使得X_i = X_2i。让mu表示从X₀到循环的开头所需的步数，lambda表示循环的长度。然后有i = mu + alambda，而2i = mu + blambda，其中a和b是整数，表示乌龟和兔子绕循环走了几次。将第一个方程式从第二个方程式中减去得到i =（b-a）* lambda，因此i是lambda的整数倍。 因此，X_{i + mu} = X_mu。X_i表示乌龟和兔子相遇的点。如果将乌龟移回起始节点X₀，并让乌龟和兔子以相同的速度继续前进，那么在走完额外的mu步之后，乌龟将到达X_mu，而兔子将到达X_{i + mu} = X_mu，因此第二个相遇点表示循环的起点。

- Jim Lewis

6

如果您能解释一下，当i是循环长度的倍数时，如何得出mu作为第一个相遇点与循环开始之间距离的结果，那将非常好。 - Passionate programmer

8

从起点开始走mu步到达循环的起始点X_mu（根据mu的定义）。然后，如果再走i步，其中i是循环长度的倍数，就会回到循环起始点：X_mu + i = X_mu。但加法是可交换的，所以这相当于走i步到达第一个相遇点X_i，然后再走mu步回到循环的起始点X_mu。 - Jim Lewis

1

@ankur：如果我写成“X_(mu + i) = X_mu”（其中(mu + i)是下标），可能会更清晰。如果你从节点X_mu开始（根据定义，这是循环的第一个节点），然后走i步，你将再次回到节点X_mu，因为i是循环长度的精确倍数。这有帮助吗？ - Jim Lewis

3

会面点是X_i，并且我们已经在我的回答的第三段证明了i必须是环长度的倍数。经过额外的mu步骤后，您现在位于X_(i + mu)处。但是我们已经展示了由于i具有特殊属性，X_(i + mu) = X_(mu + i) = X_mu，因此会面点之后的mu步骤必须将您带到循环的起始点X_mu。基本上涉及到模算术，加法的交换律。 - Jim Lewis

30

我认为你的证明存在一个小问题。因为相遇点i在循环的某一点上，所以我认为等式应该是i = mu + k + a*lambda和2i = mu + k + b*lambda，其中k是从循环开始到相遇点的步数。不过，两个方程的差是相同的。 - Ivan Xiao

显示剩余4条评论

82

_{老僧的简单而未受赞誉的答案解释了当快速跑者仅完成一次完整循环时如何找到循环。在这个答案中，我将解释当快速跑步者在慢速跑步者进入循环之前多次运行该循环的情况。}

使用相同的图像：

假设在慢跑和快跑者相遇之前，快跑者已经跑了m次循环。这意味着：

慢跑者跑过的距离：x+y
快跑者跑过的距离：x+m(y+z)+y，即他们相遇时额外的y距离

由于快跑者的速度是慢跑者的两倍，并且他们已经以相同的时间奔跑，这意味着如果我们将慢跑者奔跑的距离加倍，就会得到快跑者奔跑的距离。因此，

2（x+y）= x+m(y+z)+y

解决方案为x：

x = (m-1)(y+z)+z

在实际情况中，这意味着x=(m-1)完整的循环次数+额外的距离z。

因此，如果我们将一个指针放在列表的开头，将另一个指针留在相遇点，然后以相同的速度移动它们，将导致在循环指针完成m-1个循环运行之后，它们恰好在循环开始处相遇。

- displayName

10

有一个疑问.. 如何保证在慢速执行超过一个周期之前，它与快速速度相遇？ - siraj

6

慢指针不会按循环运行，而快指针会，因为它比慢指针跑得更快，会在慢指针进入循环之前进入循环。它们保证会相遇。如果慢指针在j+1位置，快指针在j位置，它们会在j+2位置相遇。而如果慢指针在j位置，快指针在j+1位置，这意味着它们已经在j-1位置相遇过了。 - displayName

5

如果慢指针在循环中绕了一圈，数学仍然成立：x + (y+z)m + y = 2(x+(y+z)n+y)，其中n是慢指针在相遇前绕过循环的次数。这可解为(m-2n-1)(y+z)+z=x。这意味着从相遇点开始，绕(m-2n-1)圈后，回到相遇点，再走z步，即回到循环的起点。为此，只需从头节点开始，走x个节点即可。 - mayas_mom

1

@mayas_mom：数学可能是正确的，但慢速永远无法绕过循环。它总是会被捕捉到开始或中途某个地方。 - displayName

4

x = (m - 1)(y + z) + z 可以概括为循环长度为 y+z，因为我们只关心位置。因此 x = ((m - 1)(y + z))%(y+z)) + z 这有效地等同于 x=z; - anshul garg

显示剩余8条评论

16

非常简单。您可以从相对速度的角度来考虑。如果兔子移动两个节点，而乌龟移动一个节点，则相对于乌龟，兔子移动了一个节点(假设乌龟静止不动)。因此，如果我们在循环链接列表中移动一个节点，我们肯定会再次在那个点相遇。

在找到循环链接列表内的连接点后，现在问题被缩小为查找两个链接列表问题的交点。

- murali kurapati

我非常努力地尝试理解这个答案，但是这个陈述对我来说毫无意义：“如果我们在循环链表中移动一个节点，我们肯定会再次在那个点相遇”。 - Abhijit Sarkar

12

方法：

有两个指针：

一个慢指针每次移动一个节点。
一个快指针每次移动两个节点。

如果这两个指针相遇，证明存在环。一旦它们相遇，一个节点将指向头部，然后两个节点每次移动一个节点。它们将在循环的开始处相遇。

原理： 当两个人走在一个圆形跑道上时，其中一个人的速度是另一个人的两倍，他们会在哪里相遇？正好回到起点。

现在，假设快跑者在n步圆周中领先k步。他们将在哪里相遇？恰好在n-k步处。当慢跑者走了(n-k)步时，快跑者将走k+2(n-k)步。 (也就是说，k+2n-2k步即2n-k步) 即(n-k)步（路径是圆形的，我们不关心他们相遇后走了多少圈；我们只关心他们相遇的位置）。

那么快跑者是如何领先k步的呢？因为慢跑者需要走那么多步才能到达循环的起点。所以循环的起点距离头节点有k步。

注：两个指针相遇的节点距离循环的起点（在循环内）有k步，头节点也距离循环的起点有k步。因此，当我们让这些节点平均每次前进1步时，它们将在循环的起点处相遇。

我认为这很简单。如果有任何不明确的地方，请告诉我。

- Aadith Ramia

4

请在这里发布完整答案，而不仅仅是链接，因为链接可能会在将来失效。 - Leeor

11

在第一次碰撞时，乌龟向前移动了m+k步，如上所示。兔子比乌龟快两倍，因此兔子向前移动了2(m+k)步。从这些简单的事实中，我们可以得出以下图表。

此时，我们将乌龟移到起点并宣布兔子和乌龟必须一次移动一步。根据定义，经过m步后，乌龟将位于循环的起点。而兔子会在哪里呢？

兔子也将位于循环的起点。这一点在第二个图表中很明显：当乌龟被移到起点时，兔子正好进入其最后一个循环的k步。经过m步之后，兔子将完成另一个循环并与乌龟相撞。

- skedastik

@WarrenMacEvoy 在任何时候我都没有建议他们在起点相遇。正如数据清楚地指出的那样，他们在循环开始处再次相遇。 - skedastik

5

使用高中物理101/运动学讲座中教授的相对速度概念，提供一个简单的解释。

假设从链表开始到循环开始的距离是 x。我们将循环的开始称为点 X（大写 - 见上图）。同时，我们假设循环的总长度是 N。
兔子的速度 = 2 * 乌龟的速度。因此分别为 1 跳/秒 和 2 跳/秒
当乌龟到达循环的起点 X 时，兔子必须在图中的点 Y 处再向前 x 跳（因为兔子走的路程是乌龟的两倍）。
因此，从 X 到 Y 沿顺时针方向剩余的弧长为 N-x。这也是兔子和乌龟相遇时它们之间要走的相对距离。假设这个相对距离需要时间 t_m 来走完。相对速度为 (2 跳/秒 - 1 跳/秒)，即 1 跳/秒。因此，使用相对距离 = 相对速度 × 时间，我们得到，t = N-x 秒。因此，乌龟和兔子都需要 N-x 的时间到达相遇点。
现在，在 N-x 秒的时间内，以 1 跳/秒 的速度移动，之前在点 X 的乌龟将跳 N-x 次，到达相遇点 M。因此，相遇点 M 距离点 X 顺时针方向有 N-x 跳的距离 = > 这进一步意味着，从点 M 到 X 顺时针方向还剩下 x 的距离。
但是，x 也是从链表开始到点 X 的距离。
现在，我们不关心 x 对应的跳数是多少。如果我们把一个乌龟放在 LinkedList 的起点，另一个乌龟放在相遇点 M 并让它们跳/走，那么它们会在点 X 相遇，这就是我们需要的点（或节点）。

- Pranjal Mittal

5

好的，假设兔子和乌龟在距离循环起点k步的某个地方相遇，循环开始前的步数是mu，循环长度为L。

现在在相遇点处：

乌龟覆盖的距离=mu+a*L+k - 方程1

（到达循环开头的步数+覆盖'a'个循环的步数+k步从循环开始处）（其中a是某个正常数）

兔子覆盖的距离=mu+b*L+k - 方程2

（到达循环开头的步数+覆盖'b'个循环的步数+k步从循环开始处）（其中b是某个正常数且b≥a）

因此，兔子多覆盖的距离=方程2-方程1=(b-a)*L

请注意，这个距离也等于乌龟距离起点的距离，因为兔子移动的速度是乌龟的两倍。这可以等同于“mu+k”，如果我们不包括循环的多次遍历，则也是会面点与开始点之间的距离。

因此， mu+k=(b-a)*L

因此，从这一点开始的mu步将导致回到循环的开始（因为已经走了从循环开始处的k步来到会面点）。这可能发生在同一个循环中或任何后续循环中。因此，现在如果我们将乌龟移动到链表的开头，它将需要mu步才能到达循环的起点，兔子也需要mu步才能到达循环的起点，因此它们都会在循环的起点相遇。

附言：老实说，我和原帖作者有同样的问题，我读了第一个答案，他们解释了一些事情，但我无法清楚地得出最终结果，所以我试图用自己的方式做到这一点，并发现更容易理解。

- Prateek Jassal

他们通常不会在周期开始时见面。 - Warren MacEvoy

4

将问题化简为循环问题，然后回到初始问题。

我认为以下解释更加直观。

取两个指针（1 =乌龟和2 =兔子），从头部（O）开始，1的步长为1，2的步长为2。思考当1到达该循环的起始节点（A）时的瞬间。

我们想要回答以下问题“当1在A时，2在哪里？”。

因此，OA = a是自然数（a >= 0）。但它可以用以下方式写成：a = k*n + b，其中a，k，n，b为自然数：
- n =周期长度
- k >= 0 =常量
- 0 <= b <= n-1
这意味着b = a % n。

例如：如果a = 20且n = 8 =>k = 2并且b = 4，因为20 = 2*8 + 4。

1覆盖的距离为d = OA = a = k*n + b。但是同时，2覆盖了D = 2*d = d + d = OA + d = OA + k*n + b。这意味着当2在A时，它必须覆盖k*n + b。正如您所看到的，k是圈数，但是在那些圈之后，2将离A有b远。因此，我们找到了当1在A时，2在哪里。让我们称那个点为B，其中AB = b。
现在，我们将问题简化为一个圆。问题是“会面的地方在哪里？”。那个C在哪里？

在每个步骤中，2通过1（假设为米）减少与1的距离，因为1与1之间的距离越来越远，但同时2通过2逐渐接近1。

因此，当1和2之间的距离为零时，它们相交。这意味着2减少了n - b的距离。为了实现这一点，1将进行n - b步，而2将进行2*（n - b）步。

因此，交点将在A的n - b处（顺时针方向），因为这是1遇到2

- ROMANIA_engineer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CEGRD · Accepted Answer

让我用自己的话来澄清在Wikipedia - Tortoise_and_hare提供的循环检测算法。

drawing

它是如何工作的

让我们假设有一只乌龟和一只兔子（指针的名称），它们指向具有循环的列表的开头，就像上面的图表中一样。

让我们假设如果我们每次将乌龟移动1步，兔子移动2步，它们最终会在某个点相遇。首先让我们证明这个假设是正确的。

该图说明了一个具有循环的列表。循环长度为n，我们最初距离循环m步。此外，假设当乌龟总共走i步时，它们相遇的地方距离循环开始k步。（到那时，兔子已经走了2i步。）

以下两个条件必须成立：

1) i = m + p * n + k

2) 2i = m + q * n + k

第一个说法是，乌龟移动了i步，在这些i步中，首先到达循环。然后，它通过循环p次，对于一些正数p。最后，它再经过k个节点，直到与兔子相遇。

对于兔子也是类似的。它移动了2i步，在这2i步中，它首先到达循环。然后，它通过循环q次，对于一些正数q。最后，它再经过k个节点，直到与乌龟相遇。

由于兔子的速度是乌龟的两倍，并且当它们到达相遇点时时间是相等的。

因此，通过使用简单的速度、时间和距离关系，

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

在给定的列表中，m、n、k、p、q中，前两个是属性。如果我们能够展示至少有一组值使得方程成立，即k、q、p取值的解集不为空，则说明假设是正确的。

下面是这样一组解：

p = 0

q = m

k = m n - m

我们可以验证这些值的工作方式如下：

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn

对于这个集合，i 是

i = m + p n + k

=> m + 0 * n + mn - m = mn

当然，你应该看到这不一定是最小的i。换句话说，乌龟和兔子可能已经在很多次之前相遇过。但是，由于我们表明它们至少在某一点相遇，因此我们可以说假设是正确的。因此，如果我们将其中一个移动1步，另一个移动2步，它们将必须相遇。

现在我们可以进入算法的第二部分，即如何找到循环的开始。

循环的开始

一旦乌龟和兔子相遇，让我们把乌龟放回列表的开头，并保持兔子在他们相遇的地方（距离循环开始k步）。

假设如果我们让它们以相同的速度移动（每个人走一步），那么他们再次相遇的第一次就是循环的开始。

让我们证明这个假设。

首先假设有一个神谕告诉我们m是什么。

然后，如果我们让它们移动m+k步，乌龟必须到达他们最初相遇的地点（距离循环开始k步-见图）。

先前我们表明m+k=(q-2p)n。

由于m+k步是循环长度n的倍数，因此在此期间，兔子将经过循环（q-2p）次，并回到相同的点（距离循环开始k步）。

现在，不再让它们移动m + k步，而是只让它们移动m步，那么乌龟将到达循环的起点。兔子还差k步就完成(q-2p)个旋转。由于它在循环开始时就向前迈了k步，因此兔子必须到达循环的开始处。

因此，这解释了它们第一次相遇时必须在循环的开始处相遇（因为乌龟刚刚在m步后到达循环，它永远看不到已经在循环中的兔子）。

现在，我们知道他们相遇所需移动的步数恰好是从列表开头到循环起点的距离m。当然，算法不需要知道什么是m。它将同时每次使乌龟和兔子向前移动一步，直到它们相遇。会面点必须是循环的开始，步数必须是到循环开始的距离（m）。假设我们知道列表的长度，我们也可以通过将列表长度减去m来计算循环的长度。