algorithm - 在 Floyd 循环查找算法中跳过一个以上的节点

Question

今天在看Floyd的链表循环检测算法。 我只是想知道如果我们跳过一个以上的节点会不会更好，(比如 2) 为了更快的环路检测？

例如:

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

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

Answer 1

你的建议仍然是正确的，但它并没有改变算法的速度。如果你看看wiki中的龟兔赛跑算法:

The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, x_i = x_{i + kλ}, where λ is the length of the loop to be found and μ is start position of loop. In particular, whenever i = kλ ≥ μ, it follows that x_i = x_2i.

在粗体部分，您还可以说 x_i = x_3i 或任何其他系数，但关键的洞察力是找到i，你会找到多少跳并不重要，算法的顺序取决于i的位置。