如何在链接列表中找到循环的起始节点？

Question

根据弗洛伊德的循环寻找算法,乌龟和野兔会面的点解释了链接列表中的循环性质.

为了在循环中找到起始节点,我们初始化指向列表头部的指针,并开始将野兔和乌龟指针递增一个单位.它们相遇的点表示循环的起始节点.

请告诉我它如何适用于特定情况.

链接列表如下:

1->2->3->4->5->6->7->8->3

Answer 1

让我们来看看.

你把野兔和乌龟定位在1,然后让它们奔跑,野兔的速度是乌龟的两倍.

在第0步,两者都是1.在第一步,乌龟移动到2,野兔移动到3,依此类推.

1 1
2 3
3 5
4 7
5 3
6 5
7 7 

所以兔子和乌龟在7点见面.

现在将乌龟放在开头,让它们再次运行,现在速度相同.

1 7
2 8
3 3 

所以他们确实遇到了周期的第一个元素.

这就是它如何适用于特定情况.

Answer 2

好吧,让我们保持简单.

假设您有两个跑步者A和B.每步向前移动1个节点,B移动2个节点.

如果它是循环列表,它们最终会相互见面.

那时候

说A到目前为止移动的距离是m,所以对于B来说2m

另请注意

 m = a + b
2m = a + b + k * lengthOfLoop

因为对于B,它移动了A移动的任何距离,加上k(我们不关心的一些数字)循环.a是循环点之前的距离,是循环点b之后移动的距离A.

然后我们(经过一些数学计算)

a = k * lengthOfLoop - b

现在我们把B放回到列表的头部,然后将速度降低到1.

对于B,它的a节点远离循环点.对于A,他已经通过了循环点b,并且根据上面的等式,他也是a远离循环点的节点.

因此,经过a更多步骤后,A和B将在循环点再次相遇.

Answer 3

好的,直接回答:您给出的[编辑:链接列表,而不是序列]不包含循环.这是将要发生的事情.在算法的第一部分中,乌龟和头发将分别从x1 = 2和x2 = 3开始.然后他们将前进到x2 = 3和x4 = 5.然后到x3 = 4和x6 = 7.然后到x4 = 5和x8 = 3.然后兔子将停止前进,因为除了x8之外没有任何东西,并且该算法将产生没有发现的循环.

下面我编译了一个小GIF,显示Floyd的循环发现应用于不同的序列,它确实包含循环.