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 值将增加每次迭代所采取的步数，但如果它们都是常数，则复杂度仍将是线性的。