说明如何查找循环链表中的循环开始节点工作？

我知道龟兔会议结束了循环的存在，但是如何在会议场所保持野兔的同时将龟移动到链表的起点，然后又一步一步地让它们在循环的起始点相遇呢？

Answer 1

这是Floyd的循环检测algorithm 。 您正在询问algorithm的第二阶段 – 一旦您find了一个循环的一部分，那么如何find循环的开始 ？

在Floydalgorithm的第一部分，兔子为龟的每一步移动两步。 如果乌龟和兔子相遇，就有一个循环，相遇点是循环的一部分，但不一定是循环中的第一个节点。

当乌龟和兔子相遇时，我们发现了最小的我（乌龟所采取的步数），使得X _i = X _2i 。 让mu表示从X ₀到循环开始的步数，并且让lambda表示循环的长度。 那么我= mu + a lambda，2i = mu + b lambda，其中a和b是整数，表示乌龟和兔子在周期中走了多less次。 从第二个方程中减去第一个方程给出i =（ba）* lambda，所以i是lambda的整数倍。 因此，X _{i + mu} = X _mu 。 X代表乌龟和兔子的交汇点。 如果将乌龟移回起始节点X ₀ ，并让乌龟和兔子以相同的速度继续下去，经过多less步后乌龟将达到X _亩 ，兔子将达到X _{i + mu} = X _mu ，所以第二个交汇点表示周期的开始。

Answer 2

让我试着澄清在我自己的话中http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare提供的循环检测algorithm。;

我指的是这个数字 在我的解释。

怎么运行的

让我们有一只乌龟和一只兔子（指针的名字）用一个循环指向列表的开头。

我们假设，如果我们每次移动龟一步，而一次只移动两步，他们最终会在一个点上相遇。 让我们certificate这个假设首先是真实的。

该图显示了一个循环列表。 这个循环的长度是n ，我们离开循环最初有几步。 也可以说，会议地点距离周期开始龟步距离k步，共有i步。

以下两个条件必须成立：

 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中，前两个是给定列表的属性。 如果我们可以certificate至less有一组值k，q，p使这个方程成立，我们就可以certificate这个假设是正确的。

一个这样的解决scheme如下：

 p = 0 q = m k = mn - m 

我们可以validation这些值的工作如下：

 m + k = ( q - 2p ) n => m + mn - m = ( m - 2*0) n => mn = mn. 

对于这一套， i是

 i = m + pn + k => m + 0 * n + mn - m = mn. 

当然，你应该看到，这不一定是我可能的最小的。 换句话说，龟兔可能已经遇到过很多次了。 然而，既然我们表明他们在某个时候相遇，至less我们可以说这个假设是正确的。 所以如果我们把他们中的一个移动一步，另一个移动两个步骤，他们将不得不见面。

现在我们可以进入algorithm的第二部分，即如何find循环的开始。

周期开始

一旦乌龟和兔子相遇，让我们把乌龟放回到名单的开头，并保持他们遇见的兔子（距离周期开始k步）。

假设是，如果我们让他们以相同的速度移动（两者都是1步），他们再次见面的第一次就是循环的开始。

我们来certificate这个假设。

我们先假设一些oracle告诉我们是什么。

那么，如果我们让他们移动m + k的步数，乌龟将不得不到达他们最初遇到的地方（离开周期开始k步 – 见图）。

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

由于m + k步长是周期长度n的倍数，同时，野兔将经过周期（q-2p）次并返回到同一点（离开周期开始k步）。

现在，如果我们让他们只移动m步，而不是让他们移动m + k步，龟就会到达循环的开始。 兔子在完成（q-2p）旋转的时候会走k步。 由于它在循环开始之前开始k个步骤，兔子必须到达循环开始。

因此，这解释了他们将不得不在第一次经过若干步骤之后的循环中开始会议（第一次是因为龟在步骤之后刚到达循环并且永远不会看到已经在周期）。

现在我们知道，我们需要移动它们直到它们相遇的步骤数是从列表开始到循环开始的距离，m。 当然，algorithm不需要知道什么是。 它会一次只移动乌龟和兔子，直到他们见面。 交汇点必须是循环开始，步数必须是到循环开始的距离（m）。 假设我们知道列表的长度，我们也可以计算从列表长度中减去m的周期的长度。

Answer 3

参考这个图片：

slowPointer在会议前的距离 = x + y

会议前fastPointer行进的距离 =（x + y + z）+ y = x + 2y + z

由于fastPointer的速度是slowPointer的两倍，并且在到达会议点的时间都是恒定的。

因此，通过使用简单的速度，时间和距离关系2（x + y）= x + 2y + z => x + 2y + z = 2x + 2y => x = z

因此，通过将slowPointer移动到链接列表的开头，并使slowPointer和fastPointer一次移动一个节点， 它们都有相同的距离来覆盖 。

他们将在循环开始的地方到达链表。

Answer 4

_{老和尚的简单而低估的答案解释了当快跑者只完成一个完整周期时find周期。 在这个答案中，我解释了这样的情况：快跑者在慢跑者进入循环之前已经多次运行循环。}

---

使用相同的图像：

比方说，快跑者已经慢慢跑了m次，然后慢慢相遇。 这意味着：

• 距离以较慢的速度运行： x + y
• 跑得快的距离： x + m（y + z）+ y即他们相遇的地方

由于快速运行的速度是慢速的两倍，而且它们已经运行了相同的时间，这意味着如果我们加倍慢速运行的距离，就可以快速运行。 从而，

• 2（x + y）= x + m（y + z）+ y

解决x给出，

x =（m-1）（y + z）+ z

在实际情况下，这意味着， x = （m – 1）完整的循环运行+额外的距离z 。

因此，如果我们将一个指针放在列表的开头，并将另一个指针放在会议点，那么以相同的速度移动它们将导致循环指针完成循环的m-1次运行，然后遇到另一个指针指针在循环开始。

Answer 5

在第一次碰撞时，龟如上所示移动了m + k步。 兔子移动的速度是乌龟的两倍，这意味着兔子移动了2（m + k）个步骤。 从这些简单的事实，我们可以得出以下图表。

在这一点上，我们把乌龟赶回去，宣布乌龟必须一步一个脚印。 根据定义，在步骤之后，乌龟将在循环的开始。 兔子在哪里？

兔子也将在周期的开始。 从第二张图中可以清楚地看到，当乌龟恢复到起步阶段时，兔子已经步入最后一个周期。 走了一步之后，兔子会完成另一个周期，并与乌龟相撞。

Answer 6

非常简单，你可以用相对速度来思考，如果兔子移动两个节点和龟移动一个节点，相对于龟兔正在移动一个节点（假设龟rest）。 所以，如果我们在循环链表中移动一个节点，我们肯定会再次见面。

find循环链表内的连接点后，现在问题就简化为find两个链表问题的交点。

Answer 7

好吧，让我们假设兔子和乌龟在离开循环开始k步的地方相遇，循环开始之前的步数是μ，循环的长度是L.

所以现在在会议上 – >

乌龟的距离= mu + a * L + k – 等式1

（到达循环开始的步骤+为了覆盖从循环开始的循环+ k步骤的“a”迭代所采取的步骤）（其中a是某个正常数）

距离覆盖的距离= mu + b * L + k – 等式2

（到达循环开始所采取的步骤+为了覆盖周期的'b'迭代而采取的步骤+从循环开始的k步骤）（其中b是某个正常数，b> = a）

所以兔子覆盖的额外距离是=等式2 – 等式1 =（ba）* L

请注意，这个距离也等于乌龟从起点开始的距离，因为兔子的移动速度比乌龟快两倍。 这可以等同于'mu + k'，如果我们不包含循环的多次遍历，那么它也是从开始到会合点的距离。

因此，mu + k =（ba）* L

从这一点开始，所有的步骤都会回到周期的开始（因为已经从周期开始k个步骤已经到达了交汇点）。 这可能发生在相同的周期或任何后续的周期。 因此，现在如果我们把乌龟移动到链表的开头，它将采取多达数十步的步骤来达到循环的起始点，而野兔需要多达数十步才能到达循环的开始，因此它们都会在周期的起点。

PS老实说，我脑子里有同样的问题，我读了第一个答案，他们清除了一些东西，但是我不能清楚地得出最后的结果，所以我试图以我自己的方式去做，发现它更容易理解。

Answer 8

做法：

有两个指针：

• 缓慢的指针，一次移动一个节点。
• 一个快速指针，一次移动两个节点。

如果两个指针相遇，就certificate有一个循环。 一旦遇到，其中一个节点将指向头部，然后同时进行一个节点。 他们将在循环开始时相遇。

理由：当两个人走下一条圆形轨道时，其中一个以两倍于另一个的速度行走，他们在哪里见面？ 究竟在哪里开始。

现在，假设快步跑步者以n步圈数开始k步。 他们在哪里见面？ 恰好在nk步骤。 当慢跑者已经覆盖(nk)步时， (nk)者将会覆盖k+2(nk)步。 （ 即， k+2n-2k步骤，即2n-k步骤 ）。 即(nk)步骤（path是循环的，我们不关心他们见面的轮次数量，我们只是对他们见面的位置感兴趣）。

现在，快跑者是如何首先获得k步骤的开始呢？ 因为慢跑者需要很多步骤来达到循环的开始。 所以循环的开始是从头节点开始k步。

注意：两个指针相交的节点距离循环开始k步（循环内），头节点距离循环开始k步。 所以当指针从bot这些节点以相同的步长前进时，它们将在循环开始时相遇。

我相信这很简单。 请让我知道，如果有任何部分是模棱两可的。

Answer 9

将问题简化为循环问题，然后回到最初的问题

我觉得下面的解释更直观。

1. 从头部（ O ）开始采取两个指针（ 1 =乌龟和2 =野兔）， 1步长为1，2步长为2 。 想一想当1到达该周期的开始节点（ A ）的时刻。

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

   所以， OA = a是一个自然数（ a >= 0 ）。 但是可以用下面的方式写： a = k*n + b ，其中a, k, n, b are natural numbers ：

   • 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更远。于是，我们find了2是1的时候，我们称之为B ，其中AB = b 。

   

2. 现在，我们把问题缩小到一个圆圈。 问题是“交汇点在哪里？” 。 C在哪里？

   

   在每一步中， 2减1与1的距离（比方说米），因为1与2越来越远，但同时2越接近1越2 。

   所以，当1与2之间的距离为零时，交叉点就是这样。 这意味着2减less了n - b距离。 为了达到这个目的， 1将做n - b步骤，而2将做2*(n - b)步骤。

   所以，交点将是A – （顺时针）远的n - b ，因为这是1到2的距离。 => C和A之间的距离是CA = b ，因为AC = AB + BC = n - b和CA = n - AC 。 不要认为AC = CA ，因为AC距离不是一个微不足道的math距离，而是A和C之间的步数（其中A是起点， C是终点）。

3. 现在，让我们回到最初的模式。

   我们知道a = k*n + b和CA = b 。

   我们可以取2个新指针1'和1“ ，其中1'从头（ O ）开始， 1”从交点（ C ）开始。

   当1'从O到A时 ， 1'从C到A继续完成k圈。 所以交点是A。

   

   

Answer 10

如果考虑到交汇点背后的math问题，事实certificate，他们两人将会在起点相遇。
首先让m表示循环的起始点， n表示循环的长度。 那么为了兔兔相遇，我们有：

 ( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start) 

陈述这更加math：

 (2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

所以他们会在时间t应该是周期长度的倍数。 这意味着它们在(tm) modulo n = (0-m) modulo n = (-m) modulo n的位置相遇。

所以现在回到这个问题，如果你从一个链表开始移动一个指针，另一个从交叉点移动，在m步之后，我们将会有一个（在周期内移动的）兔子来到一个点((-m) + m) modulo n = 0 modulo n这不过是循环的起点。所以我们可以看到，经过m步之后就到了循环的开始，乌龟会在那里遇到它将从链表开始遍历m个步骤。

作为一个侧面说明，我们也可以这样计算它们交点的时间：条件t = 0 modulo n告诉我们它们将在一个周期长度的倍数的时间相遇，并且t应该大于m因为他们会在周期中相遇。 所以所花费的时间将等于n的大于m的第一个倍数。

Answer 11

有了以上分析，如果你是一个学习范例的人，我试图写一个简短的分析和例子，帮助解释其他人试图解释的math。 开始了！

分析：

如果我们有两个指针，一个比另一个更快，并且将它们一起移动，它们最终会再次相遇以指示一个周期，或者为零以指示没有周期。

要find循环的起点，让…

1. m是从头到周期开始的距离;
2. d是周期中节点的数量;
3. p1是较慢指针的速度;

4. p2是更快的指针的速度，例如。 2意味着一次通过两个节点的步骤。

   观察以下迭代：

  m = 0, d = 10: p1 = 1: 0 1 2 3 4 5 6 7 8 9 10 // 0 would the start of the cycle p2 = 2: 0 2 4 6 8 10 12 14 16 18 20 m = 1, d = 10: p1 = 1: -1 0 1 2 3 4 5 6 7 8 9 p2 = 2: -1 1 3 5 7 9 11 13 15 17 19 m = 2, d = 10: p1 = 1: -2 -1 0 1 2 3 4 5 6 7 8 p2 = 2: -2 0 2 4 6 8 10 12 14 16 18 

从上面的示例数据中，我们可以很容易地发现，只要指针越来越快，指针越慢，它们就离开周期开始有m步。 为了解决这个问题，把速度较快的指针放在头部，并将其速度设置为速度较慢的指针。 当他们再次相遇时，节点就是周期的开始。

Answer 12

可以说，

 N[0] is the node of start of the loop, m is the number of steps from beginning to N[0]. 

我们有2个指针A和B，A以1倍的速度运行，B以2倍的速度运行，两者都从头开始。

当A达到N [0]时，B应该已经在N [m]中。 （注：A使用m步到达N [0]，B应该进一步m步）

然后A运行K个步骤碰撞到B，即A在N [k]，B在N [m + 2k]（注意：B应该从N [m]开始运行2k步）

在N [k]和N [m + 2k]分别碰撞B，意味着k = m + 2k，因此k = -m

因此，要从N [k]回到N [0]，我们需要更多的步骤。

简单地说，在find碰撞节点之后，我们只需要运行更多的步骤。 我们可以有一个从开始运行的指针和一个从碰撞节点运行的指针，它们在m步后会在N [0]处相遇。

因此，伪代码如下：

 1) A increase 1 step per loop 2) B increase 2 steps per loop 3) if A & B are the same node, cycle found, then go to 5 4) repeat from 1 5) A reset to head 6) A increase 1 step per loop 7) B increase 1 step per loop 8) if A & B are the same node, start of the cycle found 9) repeat from 6 

Answer 13

我认为，当他们遇到这个问题的时候，我不这么认为。 但是，如果另一个指针（F）在之前的会议点，那么是的，那个指针将会在循环的结尾，而不是循环的开始和指针（S）从列表的开始处开始最终在循环的开始。 例如：

 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8 Meet at :16 Start at :8 public Node meetNodeInLoop(){ Node fast=head; Node slow=head; fast=fast.next.next; slow=slow.next; while(fast!=slow){ fast=fast.next; fast=fast.next; if(fast==slow) break; slow=slow.next; } return fast; } public Node startOfLoop(Node meet){ Node slow=head; Node fast=meet; while(slow!=fast){ fast=fast.next; if(slow==fast.next) break; slow=slow.next; } return slow; } 

Answer 14

一个简单的解释使用相对速度的想法在高中教学 – Physics 101 / Kinematics讲座。

1. 我们假设从链表开始到圆圈开始的距离是x跳。 我们将圆的起点称为X点（大写 – 见上图）。 我们假设圆的总大小是N跳。

2. 兔子的速度= 2 *乌龟的速度。 这就是1 hops/sec和2 hops/sec

3. 当乌龟到达圆圈X的起点时，野兔必须在图中Y点进一步跳跃。 （因为兔子已经走了两次乌龟的距离）。

4. 因此，从X到Y顺时针的其余弧的长度将是Nx 。 他也恰好是兔子和乌龟之间相对的距离，以便他们能够见面 。 假设这个相对距离将在时间t_m被涵盖，即，要满足的时间。 相对速度是(2 hops/sec - 1 hops/sec)即1 hops/sec 。 因此，使用相对距离=相对速度X时间，我们得到， t = Nx ×秒。 所以这将需要Nx达到乌龟和兔子的交汇点。

5. 现在以Nx秒的时间，以1 hops/sec速度，早先在X点的龟将覆盖Nx跳，以达到会合点M 因此，这意味着会合点M在Nx逆时针方向上从X =（这进一步暗示）=>从X点到X顺时针保持x距离。

6. 但是x也是从链表开始到达点X距离。

7. 现在，我们不关心x对应的跳数。 如果我们在LinkedList开始时放一只乌龟，在会晤点M放一只乌龟，让它们跳/走，那么它们就会在我们需要的点（或节点）的X点相遇。

Answer 15

用图表工作会有所帮助。 我试图解释没有方程式的问题。

1. 如果我们让兔龟跑了一圈，然后兔子跑了两次龟，最后一圈龟兔的一半就到了。 从兔龟龟尾跑了两圈，圈数就达到了1圈。 这适用于所有的速度，如兔子跑三次，兔子1圈相当于乌龟的三分之一，因此兔子龟在3圈的末尾将会覆盖1圈，并相遇。
2. 现在，如果我们在循环之前的m个步骤启动它们，则意味着更快的兔子在循环中开始。 所以，如果龟到达循环的开始，兔子向前迈进了一步，当他们相遇的时候，在循环开始之前会有m步。

Answer 16

在这个问题的大多数解决scheme中有一个错误。 如果最后一个节点连接到第一个节点，那只是一个循环？ 如果第一次在循环的头部缓慢而快速地遇到了什么呢？ 你不会find解决scheme的正确答案。 关于如何避免这种情况，有一个正确的答案，但是给定一个快乐的path，在循环之前有许多节点k，这里是一个简单的解释：（如果你想更多地了解真正的广义解决scheme，ping我）

循环之前有k个步骤。 我们不知道k是什么，也不需要知道。 我们可以用k来抽象地工作。

– k步后

—– T在周期开始

—– H是k进入循环（他总共2k，因此k进入循环）

**现在他们已经分开了

（注意k == K == mod（loopsize，k） – 例如，如果一个节点是2步到5节点的周期，那么它也是7,12或者392步，那么周期是多less因素。

由于每个单位时间以1步的速度互相追赶，因为一个动作的速度是另一个动作的两倍，所以他们将在loopize-k上相遇。

这意味着需要k个节点到达周期的开始，因此从头到周期开始和碰撞到周期开始的距离是相同的。

所以现在第一次碰撞之后，T就回头了。 如果你以每一个的速度移动，T和H将在循环开始时相遇。 （两个都是k步）

这意味着该algorithm是：

• 从头部移动T = t.next和H.next.next直到碰撞（T == H）（有一个循环）

//通过计算循环的长度来处理k = 0或T和H在循环开始时遇到的情况

– 用计数器移动T或H，计算周期的长度

– 将指针T2移到列表的头部

– 移动循环步长的指针长度

– 移动另一个指针H2头

– 一起移动T2和H2，直到它们在循环开始时相遇

而已！

Answer 17

我知道这个问题已经有了一个可以接受的答案，但我仍然会试着以stream畅的方式回答。 假定：

 The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. Speed of tortoise : v Speed of hare : 2*v Point where both meet is at a distance 'x + b - k' from the starting point. 

现在，让兔子和乌龟从一开始就经过一段时间。

观察：

如果，乌龟旅行的距离= v * t = x +（bk）（比如说）

那么，野兔的行进距离= 2 * v * t = x +（b – k）+ b（因为野兔已经穿越了环状部分）

现在，会议时间是一样的。

=> x + 2 * b – k = 2 *（x + b – k）

=> x = k

这当然意味着不循环的path的长度与两者相遇的点的距离相同。