0

所以我的问题是，在检测循环链表的乌龟和兔子/继承人算法中，为什么只需要将第二个更快的指针增加 2 ？我无法弄清楚我在这里也没有找到任何答案。

将第一个慢指针递增 1 是有意义的，这样我们就可以遍历所有将与第二个指针进行比较的元素，但为什么更快的指针只需要递增 2。为什么我们可以将它递增 3 或 4 或更多？？？

有没有办法计算应该是什么。相对于列表中元素数量的更快指针的跳数（如果不是 2）？

4

2 回答 2

0

您可以使用 3、4 或任何您想要的方式，但使用 2 是最快的方式，因为假设您第一次处于 2 步的循环中:( D 是要走 2 步的指针，S 是普通指针。
情况1）

step 1 :x - D - x - S - x - x ...
step 2 :x - x - x - D - S - x ...
step 3 :x - x - x - x - x - SD ( match)

案例2）

step 1: x - D - S - x this is the step 2 from case 1 and we can see that this is step 2 and we also have a match

但是如果你有一个 3 步（D 应该是一次走 3 步的指针。）

情况1）

   step 1 : x - D - x - x - S ...
   step 2 : x - x - x - x - D - S ...
   step 3 : x - x - x - x - x - x - S - D ... ( D is passing S and it needs at least another loop to meet S)

案例2）

step 1 : x - D - x - S -..
step 2 : x - x - x - x - SD ( match)

案例 3)

step 1: x - D - S - ..
step 2: x - x - x - S - D ... ( D is passing S and it needs at least another loop to meet S)

因为 2 比 3、4 或任何你想要的更好，因为所有大于 2 的数字都有 1/(N-1) 的机会第一次相遇。
另一种解释方式是：对于 D 和 S 以及 N 的步长，如果 S 和 D 之间的距离为 N - 1 我们有一个匹配项（D 走 N 步和 S 1 步而不是 D = S），其他方式 D正在通过 S，所以我们有 1/(N-1) 机会第一次遇到 S 和 D，因此如果 N = 2 我们有 1 / 1 = 100% ，如果 N = 3 我们有 1/2 = 50%。
希望它有所帮助。

于 2012-06-15T11:12:42.147 回答
0

如果您使用 3 或 4 作为步长，则需要为所有特殊情况添加检查，当前进 3 可能导致第一个或第二个节点为空时。

此外，在循环的情况下，您有可能从较慢的位置与较快的位置重合的 3 个位置中的任何一个。

它只是更多的代码，更多的条件要处理，容易出错，并且使用超过 2 个似乎不太优雅，而在 Big O 方面没有任何性能提升

于 2012-06-18T07:20:07.427 回答