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 的值越大，每次迭代的步数就会增加，但如果它们都是常量，那么复杂度仍然是线性的。