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。