algorithm - 解释在循环链表中查找循环起始节点是如何工作的？

Question

我知道乌龟和兔子的 session 结束了循环的存在，但是如何将乌龟移动到链表的开头，同时将兔子保持在会合点，然后一次移动一步，使它们在循环的起点相遇？

Answer 1

这是 Floyd's algorithm for cycle detection .您是在询问算法的第二阶段——一旦您找到了一个属于循环的节点，那么如何找到循环的开始？

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

当乌龟和兔子相遇时，我们已经找到了最小的 i(乌龟走的步数)，使得 Xi = X2i。让 mu 表示从 X0 到循环开始的步数，让 lambda 表示循环的长度。然后 i = mu + alambda，并且 2i = mu + blambda，其中 a 和 b 是整数，表示乌龟和兔子绕循环的次数。减法
第二个方程的第一个方程给出 i = (b-a)*lambda，所以 i 是整数倍
lambda 的。 因此，Xi + mu = Xmu .习代表龟兔的交汇点。如果将乌龟移回起始节点X0，让乌龟和兔子以相同的速度继续前进，经过mu额外的步骤后乌龟将到达Xmu，兔子将到达Xi + mu = Xmu，所以第二个交汇点表示循环的开始。