8

根据弗洛伊德的循环查找算法，龟兔赛跑的点解释了链表中的循环性质。

为了找到循环中的起始节点，我们将 tortoise 指针初始化为链表的头部，并开始将 hare 和 tortoise 指针递增一个单位。它们相遇的点表示循环的起始节点。

请告诉我它在给定情况下是如何工作的。

链接列表如下：

1->2->3->4->5->6->7->8->3
4

5 回答 5

15

让我们来看看。

你把兔子和乌龟放在 1 处，让它们跑，兔子的速度是乌龟的两倍。

在第 0 步，两者都为 1。在第一步，乌龟移动到 2，兔子移动到 3，依此类推。

1 1
2 3
3 5
4 7
5 3
6 5
7 7

所以兔子和乌龟在 7 点相遇。

现在把乌龟放在开始处，让它们再次跑，现在以同样的速度跑。

1 7
2 8
3 3

所以他们确实在周期的第一个元素相遇。

这就是它在给定情况下的工作方式。

于 2012-06-04T14:06:10.630 回答
14

好的，让我们保持简单。

假设您有两个跑步者 A 和 B。A 每一步向前移动 1 个节点，B 向前移动 2 个节点。

如果是循环列表，他们最终会相遇。

那时候

假设 A 到目前为止移动的距离是m，所以对于 B 来说2m

另请注意

 m = a + b
2m = a + b + k * lengthOfLoop

因为对于 B，它已经移动了 A 移动的任何距离，加上k（我们不关心的一些数字）循环。a是循环点之前的距离，b是循环点之后移动的距离 A。

然后我们有（经过一些数学运算）

a = k * lengthOfLoop - b

现在我们将 B 放回列表的首位，并将他的速度降低到 1。

对于 B，它是a远离循环点的节点。对于A，他已经通过了循环点b，根据上面的等式，他也是a远离循环点的节点。

因此，经过a更多步骤，A 和 B 将在循环点再次相遇。

于 2012-06-04T18:31:14.560 回答
5

好的，直接回答：您给出的 [编辑：链表，不是序列] 不包含循环。这就是将会发生的事情。在算法的第一部分，乌龟和头发将分别从 x1=2 和 x2=3 开始。然后他们将前进到 x2=3 和 x4=5。然后到 x3=4 和 x6=7。然后到 x4=5 和 x8=3。然后野兔将停止前进，因为除了 x8 之外没有任何东西，并且算法将得出没有找到循环。

下面我编译了一个小 GIF，显示了 Floyd 的循环发现应用于不同的序列，它确实包含循环。

弗洛伊德算法在行动。

于 2012-06-04T14:04:24.637 回答
0

考虑两个指针：（fast pointer一次移动两个节点）和slow pointer（一次移动一个节点）。两者都从链表的头部开始移动。

一段时间后，进入从头开始移动k个节点slow pointer的循环，那时将遍历列表头的2k个节点。因此，这意味着指向 的第k个节点。fast pointerfast pointerslow pointer

示例：（图 1）

现在他们继续前进，直到他们在循环中的某个地方相遇。当它们相遇时，它们将远离循环的开始，与循环开始时的节点数完全相同（即循环的起始节点到节点的距离fast pointer和 相遇是k个元素（或节点）。而k也是循环起始节点到链表头的距离。slow pointerfast pointerslow pointer

（图2）

所以，我们开始从 和 的交点移动一个指针和一个fast pointer指针slow pointer。由于循环起始节点距这两个点的距离为k，因此它们将在第k步处在循环的起始节点处相遇

于 2017-01-05T19:39:29.097 回答
0
  • 假设你有一个长度为 9 的链表，将乌龟放在索引 0，兔子放在索引 1。
  • 兔子应该以 x2 的速度移动，乌龟以 x1 的速度移动，这样下次它们移动时，兔子会在索引 3，乌龟会在索引 2
  • 他们继续这样移动，直到兔子的价值等于乌龟的价值。
  • 此时，将野兔移回链表的头部（这样野兔现在在链表的头部，乌龟在它遇到野兔的索引/位置），这一次它应该只移动x1，和乌龟一样的速度。
  • 再次开始移动兔子和乌龟，如前所述，兔子和乌龟应该以 x1 的速度移动，这样如果兔子和乌龟相遇的位置在索引 6 处，那么下一步应该会导致兔子在索引 1 处，乌龟在索引 7 处。
  • 兔子和乌龟再次相遇的下一个点是这个链表上循环的开始。
于 2021-01-20T21:06:55.287 回答