algorithm - 仅在 Floyd 循环查找算法中将快速指针增加 2

Question

我正在通过弗洛伊德的循环查找算法并且有一个疑问。

我们是否只将快速指针增加 2？

是否有任何其他值应该是最匹配的？

Answer 1

假设两个指针都在一个循环中结束。相对于彼此，快速指针在每次迭代中向慢速指针移动 1 个单位。这意味着在某些时候指针必须重叠。这是一个方便的属性。

我想你可以用 3 速和 2 速指针来做，但它不会更快，代码会更复杂（必须每一步写出对三个指针的检查，而不仅仅是 2 个）。

Answer 2

如果您将快速指针的值增加两个以上，您可能会“跳过”两个指针重叠的值，最终不得不迭代更多次。

通过将快速点增加 2，您可以保证在最坏的情况下最大限度地提高效率。