java - 检测链表中的循环 - 指针何时相遇？如何通过交集找到循环的头部？

Question

这个问题是关于: How to detect a loop in a linked list?

我已经理解了解决方案，但我不理解我在某本书中读到的两个陈述-

1. 如果 L 是循环的长度，n 是节点数，慢指针和快指针将在 n x L 长度处相遇 - 这是否正确？如果没有，他们什么时候见面？谁能用简单的术语解释一下。

2. 为了找到循环的头部，在慢速指针和快速指针相遇后，我们将慢速指针移动到头部并将两个指针移动 1 个节点，直到它们在循环的头部相交 - 如何将慢速指针移动到头部然后将两个指针移动 1 个节点是否会使它们在循环开始时相遇？

Answer 1

在从头开始进入循环之前，您需要遍历 N - L 个节点。 (其中N为除初始节点外的节点总数)

令S和F分别为慢指针和快指针遍历的节点数。

为了使两个节点相遇，2 * S = F = S + x * L 其中 x 是一个整数。因此 S 将是 L * ceiling( N/L )。

如果您移动 N - L 个节点，您将到达循环的起点。