逻辑，以确定循环链表

Question

在最好的方法来检测一个循环链表，我们执行以下操作：

1. 用弗洛伊德的循环查找算法中的识别位置在一个链表中循环。
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。