algorithm - 识别链表中循环的方法背后的逻辑

Question

在检测链表中的循环的最佳方法中，我们执行以下操作：

1. 使用 Floyd 的循环查找算法并在链表中识别循环内的位置。
2. 计算链表中循环的大小
3. 将一个指针定位在列表的开头，另一个“k”（其中 k 是循环的大小）定位。
4. 在迭代中，它们在循环开始时相遇。

我想知道为什么会这样。这背后的一些理论逻辑？

Answer 1

Floyd 方法可以帮助您检测到有一个循环，但由于在循环开始之前可能存在一些节点，它不能直接给您循环的长度。所以你应该在下一步计算长度。现在我们要找出循环的起点。考虑，循环的长度是K，从头节点到循环开始的节点数是L，现在如果你向前移动两个指针，它们会在循环的开始处相遇，因为头指针必须向前移动L节点和指针哪个K步骤前面有两种可能。它肯定会在L节点之后的循环开始，因为： 选择 1：如果它在循环中，它在K-L循环和 的节点上K-(K-L) = L。选择 2：如果它超出循环，L-K则节点保留到开始和L-K + K = L.