小编典典

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

all

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


阅读 103

收藏
2022-07-09

共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,因此第二个交汇点表示开始循环。

2022-07-09