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

Question

如何在给定的链表中找到循环的起始节点？我们称之为“循环点”

目前，我已经了解以下内容（使用慢/快指针）：

1.假设列表具有大小为k的非循环部分 2.慢移动k步 3.快速移动2k步 4.快速是(2k-k)= k步"超前"慢速的 5.慢指针位于循环的开头；也称为“循环点” 6.快速从“循环点”或此时的慢指针“后面”的(LOOP_LENGTH-k)步 7.对于每1步缓慢移动，快速移动2步并通过1步赢得慢速。 8.因此，快速需要(LOOP_LENGTH-k)步才能遇到慢速并相撞 9.这是我不理解的一步： “在这个碰撞点，两个节点将距离循环的前端 k 步。” 10.找到碰撞点后，将一个指针移动到列表的头部。 11.现在以1步/轮的速度移动两个指针，直到它们相撞。它们同时相遇的节点即为循环的开始，因此为“循环点”。

有人可以请解释第9步及其后续步骤吗？

谢谢

- brainydexter

Answer 1

您的第六点有误，此时快指针仍然距离慢指针k步，而慢指针已经到达循环点；最好使用“ahead”或“behind”，而不是“away”。另外，k可能比loop_length小、大或相等。因此，在到达循环点时，快指针比慢指针超前k步；在一个循环中，快指针比循环点超前k%loop_length步。如果k = some_n * loop_length + r，则快指针比循环点超前r步，即r := k % loop_length。

但这意味着慢指针在循环中领先快指针loop_length - r步。毕竟这是一个循环。因此，经过loop_length - r个额外的步骤，快指针将追上慢指针。对于每一步慢指针移动的距离，快指针会向前移动两个步。

因此，我们不知道k，也不知道loop_length或r，我们只知道m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length。直到两个指针相遇的总步数m是循环长度的倍数。

现在我们重新开始，新的指针位于起点，慢指针与快指针相遇的位置前进了m步。我们以相同速度移动新的和慢的指针，每次移动1步，在循环点处它们将相遇——因为当新指针到达循环点时，第二个指针仍然领先m步，也就是说，在环上沿着循环走m％loop_length==0步。这样我们就可以找出k是多少（我们一直在计算步数），以及循环点。

通过再次沿着循环行进，直到两者再次相遇，我们找到了loop_length。

参见：http://en.wikipedia.org/wiki/Cycle_detection#Algorithms。

- Will Ness

---

你能解释一下这个关系吗？m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length？ - brainydexter

我刚刚替换了这些值。 :) 两个指针相遇所需的总步数是多少？我们说在循环点之前有 k 步；当慢指针在 k 处时，快指针比慢指针超前 r = k％loop_length；也就是说，慢指针比快指针超前 loop_length-r - 因为慢指针位于循环点，如果我们将它到快指针的距离加起来，再从快指针向它的距离，我们得到 loop_length。这就是拥有循环的含义。而 r = k％loop_length 意味着 k = some_n * loop_length + r，其中 some_n 是某个值（包括可能为0）。因此，m = k + loop_length - r。 - Will Ness

慢指针比快指针超前 loop_length - r 步，因此快指针需要 loop_length - r 步才能追上慢指针，它们会在某个地方相遇。总步数将是 m = k + loop_length - r。 - Will Ness

啊哈！我想我明白了 :) 总结一下，快指针首先走了（2k：=）k（非循环），然后进入循环的r步。此时，慢指针在循环点处，并且比快指针超前了loop_length-r步。快指针将在恰好loop_length-r步中追上慢指针。因此，m = # of steps for pointers to meet; => m = k + (loop_length - r)。这个代换也产生了loop_length的some_n factor。 - brainydexter

此外，之后也很容易找到一个有环链表的长度 :). 我希望我能够点赞更多！ - brainydexter

很高兴能帮忙，现在我自己也更好地理解了。 :) 好吧，既然你问了， :) 你可以设置一个赏金，在24小时后将其授予你选择的答案。但这并不是必要的，真的。 - Will Ness

Answer 2

嗯...这种问题很难解释，除非你面对面交谈。我会试一试。

首先，在第6步中：我认为快指针应该离圆点有k的距离。

但是不要管那些了。我们现在有两辆车。一辆快车速度是慢车的两倍。

假设快车从圆形赛道上以k的距离开始。

而慢车从圆点开始。

现在我说，两辆车都会在圆点之前k的距离相遇。

为什么？因为最初快车距离圆点有k的距离。当完成第一次圆周时，快车将行驶n的距离。现在快车再次距离圆点有k的距离。但是慢车距离圆点有n/2的距离。

现在，快车必须再行驶 n-2k 的距离才能到达圆点前的 k 距离。而慢车必须行驶 n/2 - k = (n-2k) / 2 的距离才能到达起点前的 k 距离。这恰好是快车要行驶路程的一半。而快车的速度是慢车的两倍。

所以，显然他们会在距离圆点前的 k 处相遇。

- dejavu

---

我想指出的一件事是，在循环内部，快速指针永远不会超过慢速指针。它们将会发生碰撞。原因在于：慢速指针位于i处，而快速指针位于i-1处。当它们移动时，慢速指针指向i+1，快速指针也是i+1，从而发生碰撞。或者，慢速指针处于i，而快速指针处于i-2。下一步，慢速指针指向i+1，快速指针指向i。再下一步，慢速指针指向i+2，快速指针指向i+2，再次发生碰撞。所以快速指针永远无法超过慢速指针，只能在循环内部发生一次碰撞！ - brainydexter