如何在给定的链表中找到循环的起始节点？我们称其为循环点
到目前为止，我已经了解以下内容（使用慢/快指针）：
- 假设列表有一个非循环部分的大小
k
- 缓慢移动 k 步
- 快速移动 2k 步
- 快的是 (2k - k)=
k steps ahead of slow
- 慢是在循环的开始；也称为
Cycle point
- fast is
(LOOP_LENGTH - k) steps behind from Cycle point或此时的慢指针
- 缓慢移动每 1 步，快速移动 2 步，慢速移动 1 步。
- 因此，需要快速
(LOOP_LENGTH - k)脚步缓慢相遇并碰撞
- 这是我不明白的步骤：在这个碰撞点，两个节点都会
k从循环的前面开始的步骤。
- 一旦找到碰撞点，将一个指针移动到列表的头部。
- 现在以 1 步/转的速度移动两个指针直到碰撞。它们相遇的节点是循环的开始，因此
Cycle point
有人可以解释一下第 9 步及其之后的内容吗？
Thanks
EDIT:
我想指出的一件事是，一旦进入循环，快指针永远不会超过慢指针。他们会发生碰撞。原因如下：慢速假设为 i，而快速假设为 i-1。当它们移动时，slow=> i+1，fast也将在i+1，因此发生碰撞。或者，慢速位于 i，快速位于 i-2。下一步，慢-> i+1；快：i.下一步，慢-> i+2，快：i+2，因此再次碰撞。太快的永远无法超越慢的，只会在循环内碰撞一次！
你的6.错了，快指针距离当时处于循环点的慢指针还有k步；但更好地利用ahead or behind代替away. Plus, k可能更小、更大或等于loop_length.
所以，快速指针是k当到达循环点时，它会领先于慢速循环，根据您的假设，k开始后的步骤。现在，在循环上测量，快速指针是k % loop_length比循环点提前的步数。正确的？如果k = some_n * loop_length + r，快速指针为r比循环点提前一步，也就是说，r := k % loop_length领先一步。
但这意味着慢指针是loop_length - r steps 领先于快者，沿着环路。这是一个loop毕竟。所以之后loop_length - r快指针将追上慢指针的附加步骤。对于每一步，慢速指针移开，快速指针移近two steps.
所以我们不知道k，我们不知道loop_length or 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 http://en.wikipedia.org/wiki/Cycle_detection#Algorithms
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
