解释循环链表中查找循环开始节点的工作原理？

这是Floyd的循环检测算法。您在询问算法的第二阶段 - 一旦您找到了一个循环的节点，如何找到循环的开始？在弗洛伊德算法的第一部分中，野兔为乌龟的每一步移动两步。如果乌龟和野兔相遇，则存在一个循环，并且会合点是循环的一部分，但不一定是循环中的第一个节点。当乌龟和野兔相遇时，我们发现了最小的i（乌龟所采取的步数），使得Xi = X2i。设mu表示从X0到循环开始的步数，让lambda表示循环的长度。然后i = mu + alambda，2i = mu + blambda，其中a和b是整数，表示乌龟和野兔在周期中走了多少次。减法第二个方程式给出i =（b-a）* lambda，所以i是整数倍兰达因此，Xi + mu = Xmu。习代表了乌龟和野兔的交汇点。如果你将乌龟移回起始节点X0，让乌龟和野兔以相同的速度继续下去，经过额外的步骤，乌龟将到达Xmu，野兔将达到Xi + mu = Xmu，所以第二个会合点表示循环的开始。

拟蓬

让我试着用我自己的话来澄清http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare提供的循环检测算法。我在解释中参考了这个数字。这个怎么运作让我们有一只乌龟和一只野兔（指针的名字）指向一个循环的列表的开头。让我们假设，如果我们一步一步地移动一步，一次只有两步，它们最终会在某一点上相遇。让我们说明首先这个假设是正确的。该图说明了一个带循环的列表。循环的长度为n，我们最初距离循环m步。另外，我们可以说会议点距离周期开始是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中，前两个是给定列表的属性。如果我们可以证明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.

当然，你应该看到这不一定是我可能的最小。换句话说，乌龟和兔子可能已经多次见过面了。然而，由于我们表明它们至少在某个时刻相遇，我们可以说假设是正确的。因此，如果我们将其中一个移动一步，而另一个移动一步两步，则必须满足。现在我们可以进入算法的第二部分，即如何找到循环的开始。循环开始一旦乌龟和野兔见面，让我们把乌龟放回到清单的开头，并将野兔放在他们遇到的地方（距离循环开始的k步）。假设是，如果我们让它们以相同的速度移动（两者都是1步），它们第一次再次相遇将是循环的开始。让我们来证明这个假设。让我们首先假设一些oracle告诉我们m是什么。然后，如果我们让它们移动m + k步，那么乌龟必须到达它们最初遇到的点（距离循环开始k步 - 见图）。以前我们展示了m + k = (q - 2p) n。由于m + k步长是周期长度n的倍数，因此，平均时间内的野兔将经历周期（q-2p）次并且将返回到相同点（距离周期开始k步）。现在，不是让他们移动m + k步，如果我们让他们只移动m步，乌龟就会到达循环开始。野兔将完成（q-2p）轮换。由于它在循环开始前开始了k步，因此野兔必须在循环开始时到达。结果，这解释了他们必须在第一次经过一些步骤后才开始在周期开始见面（这是第一次因为陆龟在m步之后到达周期而且它永远不会看到已经存在的野兔周期）。现在我们知道我们需要移动它们直到它们相遇的步数变成从列表开头到循环开始的距离，m。当然，算法不需要知道m是什么。它会一次一步地移动乌龟和野兔，直到它们相遇。会合点必须是循环开始，步数必须是循环开始的距离（m）。假设我们知道列表的长度，我们还可以计算从列表长度中减去m的周期的长度。

鞋扣蚊冈借

参考此图片：在meeting = x + y之前slowPointer行进的距离 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一次移动一个节点，它们都具有相同的距离。它们将在链接列表中的循环开始点到达。

抚驰

Old Monk的简单和低调的答案解释了当快速跑步者仅完成单个完整周期时找到周期。在这个答案中，我解释了当慢速跑步者进入循环之前快速跑步者多次运行循环的情况。使用相同的图像：让我们说快速跑步者在缓慢和快速相遇之前已经运行了几次。这意味着：距离慢：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。因此，如果我们将一个指针放在列表的开头并将另一个指针留在会合点上，那么以相同的速度移动它们将导致in循环指针完成m-1次循环运行然后满足另一个指针就在循环开始处。

炬卤遁蝎变

在第一次碰撞时，如上所示，乌龟移动了m + k步。野兔的移动速度是龟的两倍，这意味着兔子移动了2（m + k）步。从这些简单的事实我们可以得出以下图表。在这一点上，我们将乌龟移回到起点并宣布兔子和乌龟必须一步一步地移动。根据定义，在m步之后，乌龟将处于循环的开始。兔子在哪里？野兔也将在周期的开始。从第二张图中可以清楚地看出：当乌龟移回到开始时，兔子进入最后一个循环。在几步之后，野兔将完成另一个循环并与乌龟相撞。

攫怂绵十

这非常简单。你可以考虑相对速度。如果兔子移动两个节点并且乌龟移动一个节点，则相对于兔子移动一个节点（假设休息时的乌龟）。因此，如果我们在循环链表中移动一个节点，我们肯定会在那时再次遇到。找到圆形链表内的连接点后，现在问题减少到找到两个链表问题的交点。

癸痊醒

好吧让我们假设野兔和乌龟在距离循环开始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. 请注意，这个距离也等于乌龟距离起点的距离，因为野兔的移动速度比乌龟快2倍。这可以等同于'mu + k'，如果我们不包括循环的多次遍历，它也是会合点距起点的距离。从而， mu + k =（b-a）* L. 因此，从这一点开始的步骤将导致回到循环的开始（因为已经采取了从循环开始的k步骤到达会合点）。这可能发生在同一周期或任何后续周期中。因此，现在如果我们将乌龟移动到链表的开头，它将需要mu步骤到达循环的起始点，野兔将采取mu步骤也到达循环的开始，因此它们都将在循环的起点。附：老实说，我在脑海中遇到了与原始海报相同的问题，我读到了第一个答案，他们确实清除了一些事情，但我无法清楚地得到最终结果，所以我试图按照自己的方式去做，然后找到了它更容易理解。

降女陷费券

做法：有两个指针：一个慢速指针，一次移动一个节点。一个快速指针，一次移动两个节点。如果两个指针相遇，则证明存在循环。一旦他们遇到，其中一个节点将指向头部，然后一次都进行一个节点。他们将在循环开始时见面。理由：当两个人沿着圆形轨道行走时，其中一个人的速度是另一个人的两倍，他们在哪里见面？正是他们开始的地方。现在，假设快速跑步者在n步圈中有一个k步的头部开始。他们会在哪里见面？恰好在n-k步。当慢速跑步者已经(n-k)步时，快速跑步者将覆盖k+2(n-k)步。（即，k+2n-2k步骤即2n-k步骤）。即(n-k)步（路径是圆形的，我们不关心它们相遇之后的轮数;我们只对它们相遇的位置感兴趣）。现在，快速跑步者是如何首先获得k步骤的先机？因为慢跑者花了很多步才到达循环的开始。所以循环的开始是从头节点开始的k步。注意：两个指针相遇的节点距离循环开始（循环内部）k步，并且头节点距离循环开始也是k步。因此，当我们从这些节点的机器人以相同的步长前进时，它们将在循环开始时相遇。我相信这很简单。如果任何部分含糊不清，请告诉我。

钨蜡唤喉晤

将问题减少到循环问题，然后回到最初的问题我发现以下解释更直观。从头部（O）开始取两个指针（1 =乌龟和2 =野兔），1的步长为1,2，步长为2.想想1到达该循环的起始节点的时刻（一个）。我们想回答以下问题“当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。所以，我们发现当1在A中时2是2.让我们称之为B，其中AB = b。现在，我们将问题缩小到一个圆圈。问题是“会面点在哪里？”。 C在哪里？在每一步中，2减少距离1与1（比如米），因为1与1的距离越来越远，但同时2越接近1由2。因此，交点将是1到2之间的距离为零。这意味着2减少了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距离不是一个微不足道的数学距离，它是A和C之间的步数（其中A是起点，C是终点）。现在，让我们回到初始架构。我们知道a = k*n + b和CA = b。我们可以采用2个新指针1'和1''，其中1'从头部开始（O），1'从交叉点（C）开始。当1'从O变为A时，1'从C变为A并继续完成k圈。所以，交点是A.

梦话快家腹

如果指针在如图所示的点P处相遇，则距离Z + Y是点P，而X + Y也是点P，这意味着Z = X.这就是为什么保持从P移动一个指针并从开始（S）移动另一个指针直到它们相遇为止的原因，这意味着将相等距离（Z或X）移动到相同的点M（距离S的距离Z和距离S的距离为Z）将是开始循环。简单！

闯舱酮

图像信用调用指针所遵循的链接数量，以及算法将慢指针移动一个链接和快速指针两个链接所需的迭代次数。在长度为C的循环之前有N个节点，用循环偏移k = 0到C-1标记。要达到循环的开始，慢需要N个时间和距离。这意味着在循环中快速取N距离（N到达那里，N到旋转）。所以在时间N，慢是在循环偏移k = 0，而快速是在循环偏移k = N mod C. 如果N mod C为零，则慢速和快速现在匹配，并且在时间N和循环位置k = 0处找到循环。如果N mod C不为零，则快速现在必须赶上慢速，其在时间N处于循环中的C-（N mod C）距离后面。由于每1次慢速快速移动2，在每次迭代时将距离减小1，因此这需要与时间N处的快速和慢速之间的距离一样多的额外时间，即C-（N mod C）。由于慢速从偏移0开始移动，这也是它们相遇的偏移量。因此，如果N mod C为零，则在循环开始的N次迭代之后阶段1停止。否则，阶段1在偏移C-（N mod C）的N + C-（N mod C）迭代之后停止进入循环。

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

好吧，所以阶段2：慢需要N个步骤才能到达循环，此时快速（现在每步移动1步）处于（C-（N mod C）+ N）mod C = 0.所以它们相遇在第2阶段之后的周期开始时。

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

为了完整性，阶段3通过在循环中再次移动来计算循环长度：

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

蹄渭信妥扳

通过上述所有分析，如果您是一个逐个学习的人，我试着写一个简短的分析和示例，帮助解释其他人试图解释的数学。开始了！分析：如果我们有两个指针，一个比另一个快，并将它们一起移动，它们最终将再次相遇以指示一个循环或null以指示没有循环。要找到周期的起点，让...... m是从头部到周期开始的距离; d是循环中的节点数; p1是较慢指针的速度; 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步。要解决此问题，请将较快的指针放回头部并将其速度设置为较慢指针的速度。当它们再次相遇时，节点就是循环的开始。

枫湃揩乾纲

比方说，

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以1x速度运行，B以2x速度运行，两者都从头开始。当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]，我们需要更多步骤。简单地说，我们只需要在找到碰撞节点后再运行几步。我们可以有一个从开始运行的指针和一个从碰撞节点运行的指针，它们将在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

稍惮

我不认为这是真的，当他们遇到那是起点。但是如果另一个指针（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;
}

期差骇蓟

使用高中教授的相对速度思想的简单解释 - 物理101 /运动学讲座。让我们假设从链表开始到圆圈开始的距离是x跳。让我们将圆圈的起点称为点X（在上限中 - 见上图）。我们还假设圆的总大小是N跳。野兔的速度= 2 *龟的速度。那分别是1 hops/sec和2 hops/sec 当乌龟到达X的圆圈开始时，野兔必须在图中的Y处进一步x跳。（因为野兔已经走过了两倍于乌龟的距离）。因此，从X到Y顺时针的剩余弧长为N-x。这也恰好是野兔和乌龟之间能够相遇的相对距离。假设这个相对距离将在时间t_m，即见面时间内被覆盖。相对速度为(2 hops/sec - 1 hops/sec)，即1 hops/sec。因此，使用相对距离=相对速度X时间，我们得到，t=N-x秒。因此，乌龟和兔子的交汇点将达到85英镑。现在在N-x秒的时间和1 hops/sec的速度，早于X的乌龟将覆盖N-x跳跃到达会合点M。因此，这意味着会合点M从X逆时针方向N-x跳跃（=进一步暗示）=>顺时针方向从M到X剩余x距离。但是x也是从链表开始到达X点的距离。现在，我们不关心x对应的跳数。如果我们在LinkedList的开头放一只乌龟，在会合点M放一只乌龟，让它们跳/走，那么它们将在X点相遇，这是我们需要的点（或节点）。

荒劫娇噬

使用图表进行此操作会有所帮助。我试图解释没有方程的问题。如果我们让野兔和乌龟在一个圆圈中运行，然后野兔运行两次乌龟，那么在一圈结束时野兔乌龟就会变成一半。在野兔龟两圈结束时，他们将完成1圈，他们都会相遇。这适用于所有速度，如果野兔跑三次，野兔1圈等于龟的1/3，所以在3圈结束时，野兔龟将覆盖1圈并且它们相遇。现在如果我们在循环之前开始它们，那么这意味着更快的野兔在循环中开始。因此，如果乌龟到达循环的开始，野兔就会向前迈出几步，当它们相遇时，它将在循环开始之前的几个步骤。

悸翠疮武昏

- 循环前有k步。我们不知道k是什么，也不需要知道。我们可以用k来抽象地工作。 - 经过k步 ----- T处于循环开始阶段 ----- H是进入循环的k步（他总共2k，因此进入循环） **他们现在循环 - k分开（注意k == K == mod（loopsize，k） - 例如，如果一个节点是进入5节点周期的2步，那么它也是7,12或392步，所以周期有多大wrt k没有考虑到。因为它们以每单位时间1步的速度相互追赶，因为一个移动速度是另一个的两倍，它们将在loopize-k处相遇。这意味着它将需要k个节点到达循环的开始，因此从头到开始和碰撞到循环开始的距离是相同的。所以现在在第一次碰撞后将T移回头部。如果你以每个1的速度移动，T和H将在cyclestart上相遇。（两个步骤为k）这意味着该算法是：从头部移动T = t.next和H.next.next直到它们碰撞（T == H）（有一个循环） //当k = 0或T和H在循环的头部遇到时，处理大小写计算循环的长度 - 通过用计数器移动周围的T或H来计算周期的长度 - 将指针T2移动到列表头部 - 移动循环步骤的指针长度 - 将另一个指针H2移到头部 - 同时移动T2和H2，直到它们在循环开始时相遇而已！

峨躬坎抬焚

我知道这个问题已经有了一个公认的答案，但我仍然会以流畅的方式回答。假设：

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 +（b-k）（比如说）然后，野兔行进的距离= 2 * v * t = x +（b-k）+ b（因为野兔已经遍历了环状部分）现在，会议时间是一样的。 => x + 2 * b - k = 2 *（x + b - k） => x = k 这当然意味着未循环的路径的长度与循环的起始点距离两者相遇的点的距离相同。

捻盒愧杯

如果你考虑会面点背后的数学，那么很容易证明他们都会在起点上相遇。首先让m表示链表中循环的起点，n表示循环的长度。然后为野兔和乌龟见面，我们有：

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

用数学方式说明这一点：

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

所以他们将在时间t见面，这应该是周期长度的倍数。这意味着他们在一个地方见面，这是 (t-m) 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，因为它们会遇到在周期中。因此，所花费的时间将等于大于m的n的第一个倍数。

解释循环链表中查找循环开始节点的工作原理？

19 个回复

发起人

floyd_cycle_finding

问题状态

解释循环链表中查找循环开始节点的工作原理？

与内容相关的链接

19 个回复

发起人

floyd_cycle_finding

问题状态