如何在循环链表中查找循环起始节点？

Question

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

Answer 1

这是Floyd
的循环检测算法
。你在问算法的第二阶段——一旦你找到了一个属于循环的节点，如何找到循环的
开始 ？

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

当乌龟和兔子相遇时，我们找到了最小的 i（乌龟走的步数），使得 X i = X 2i。让 mu 表示从 X 0到循环开始的步数，让 lambda
表示循环的长度。然后 i = mu + a lambda 和 2i = mu + b lambda，其中 a 和 b
是整数，表示龟兔赛跑了多少次。从第二个方程中减去第一个方程得到 i = (ba)lambda，所以 i 是 lambda 的整数倍。 因此，X i +
mu = X mu*。X i代表龟兔赛跑的交汇点。如果将乌龟移回起始节点 X0，让龟兔以同样的速度继续前进，经过 mu 个额外的步骤，乌龟将达到 X
mu，而兔子将达到 X i + mu = X mu，因此第二个交汇点表示开始循环。