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

Question

在链表中检测循环的最佳方法是:

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

我想知道为什么这工作。这背后有什么理论逻辑吗?

Answer 1

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