algorithm - 在 Floyd 循环查找算法中跳过多个节点

Question

今天我正在阅读 Floyd 的在链表中检测循环的算法。我只是想知道如果我们跳过多个节点（比如 2 个）以更快地进行循环检测会不会更好？

例如：

fastptr=fastptr->next->next->next.

请注意，更改时会考虑副作用fastptr。

Answer 1

您的建议仍然是正确的，但它不会改变算法的速度。如果您查看wiki中的龟兔算法：

该算法的关键在于，对于任何整数 i ≥ μ 和 k ≥ 0，x _i = x _{i + kλ}，其中 λ 是要找到的循环的长度，μ 是循环的开始位置。特别是，只要 i = kλ ≥ μ，则x _i = x _2i。

在粗体部分，您也可以说x _i = x _3i或任何其他系数，但关键的见解是找到i，您会找到多少次跳跃并不重要，算法的顺序取决于我。