2

下面是使用 Floyd 的慢速算法发现列表中存在循环后的代码。

我们如何确定 begin 和 tortoise 会在循环的开始处相遇？

Node begin = head;
tortoise = tortoise.next;
while (begin != tortoise) {
    begin = begin.next;
    if (tortoise.next == begin) {        // Find the position of the loop and mark the node as null

        tortoise.next = null;
        return;
    }
    tortoise = tortoise.next;
}

任何帮助，将不胜感激！

4

2 回答 2

2

图表供参考

让我们看看您发布的代码之前的第一部分。

考虑

  • 一个慢速指针（乌龟）和一个快速指针（野兔）。快速指针的移动速度是慢速指针的两倍，因此当慢速指针移动距离“d”时，快速指针移动距离“2d”。
  • 从起点到交点的长度为 x（参见图表）。
  • 它们在距离交叉点长度为 y 的随机点相遇（参见图表）。
  • 从交点到交点的长度为z（参考图表）。
  • 循环长度为 y+z；
  • 当慢与快相遇。慢速已覆盖距离 x+y （例如 d）

  • fast 已覆盖距离 x+y+z+y （将为 2*d）

  • 2*d= x+2y+z

  • 2(x+y)= x+2y+z

  • 2x+2y=x+2y+z

  • x=z（已证明）

现在来到您发布的代码。

因为已经证明在第一个交汇点之后 x 将等于 z（假设兔子的速度是乌龟的两倍）然后从起点移动一个指针，从第一个交汇点移动一个指针到交点（即循环的起点）。

于 2019-10-03T11:19:56.127 回答
1

这个想法是两个指针以不同的速度移动。所以nextoftortoise可能会跳跃一个元素，而nextof begin（我认为它通常被称为hare）可能会跳跃更多。如果你同时增加它们并且有一个循环，一个会在某个时候赶上另一个。

于 2019-10-03T10:37:42.973 回答