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

Question

我知道Tortoise和Hare的会议总结了循环的存在，但是如何将乌龟移动到链接列表的开头，同时又将野兔保留在会场，然后一次移动两个步骤，使它们在循环的起点相遇呢？

Answer 1

这是用于循环检测的弗洛伊德算法。您正在询问算法的第二阶段-
找到一个节点是周期的一部分后，如何找到周期的 起点 ？

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

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