algorithm - 不同步长的 Floyd 环路检测算法

Question

在链表中的Floyd 循环检测算法中，我们一般将慢指针加 1 个单位，快指针加 2 个单位。我们可以使用哪些其他值来增加慢速和快速指针，它们如何改变算法的复杂性？

Answer 1

无论速度或环路大小如何，这两个指针总是会相遇。

使用以下值：

• a和b：每个指针每次迭代所采取的步数。
• m：循环中的节点数。

在i迭代之后，两个指针将已经采取ai和bi步骤。i如果足够大以至于两个指针都在循环内，它们将位于同一个节点，并且：

ai = bi (mod m)

这与以下内容相同：

(a-b)i = 0 (mod m)

这对于一个值i是 的倍数m且足够大的值是正确的。这样的值将始终存在，因此指针将始终相遇。

a和的较大值b将增加每次迭代所采取的步数，但如果它们都是常数，那么复杂度仍然是线性的。

Answer 2

I think the step size does not matter. As long as slow < fast the two would meet if there is a cycle in the list.

The only difference would be that in each iteration the number of steps taken by each pointer would vary.

Answer 3

好吧，我通过使用一些基础数学以一种争论的方式理解了它。想象一个带有循环的链表，慢指针和快指针都开始移动。令 T 为循环开始的点或列表连接自身的节点。当慢速指针到达该节点时，快速指针现在将位于循环内。所以现在想象这个像时钟一样的循环有一个时针和一个分针，这两个指针会在它们速度的公倍数上相遇，而不管它们的速度如何。