0

有一种明显的标准方法来查找链表是否具有循环，然后返回循环开始处的节点，这是具有慢/快指针的 floy 算法。
代码和逻辑很清楚，除了 1 件事。
该方法基于这样的假设，即指针将遇到的循环中的节点与从列表头部到循环开始的步数完全相同。那部分是我不明白的。
因此，如果 Slow 和 Fast 都从列表的头部开始，当 Slow 完成 k 步并到达循环的开头时，Fast 将完成 2k 步并且实际上是 k 步进入循环。
如此快的速度领先于慢速 k 步，落后于慢速（在循环的开始处） N - k 其中 N 是循环大小。
由于在每一步中，快接近慢，而快在慢 N - k 节点之后，快将在 N - k 步骤中变慢。
此时，slow 将执行 N - k 步，并将在节点 N - k 中。
Fast 将完成 2(N - k) 步，并将在节点 2N - 2k + k = 2N - k 处（因为 fast 在节点 k 处）。
由于这是一个循环 2N - k = N - k，因此它们在节点 N - k 处相遇。
但是为什么 N - k 节点距离循环开始有 k 步？
我在这里有什么误解？

4

2 回答 2

0

让我给你另一种看待这个问题的方法，最后，你可能也会得到你的答案。

用于解释的变量：

  • N - linkedlist 中的节点链接总数。
  • C - 从头部到循环起点的距离
  • Y - 从循环起点到汇合点的距离。
  • K - 从会合点到循环起点的距离。

因此，我们可以从这些变量中得出一些结论。

  1. N = C + Y + K
  2. 慢速指针覆盖的距离 - Ds = C + Y
  3. 快速指针覆盖的距离 - Df = N + Y

代表

这里 ，

  • N = 12
  • C = 2
  • 两个指针将在节点号 11 处相遇，因此 Y = 8
  • K = 2

因为我们知道快指针比慢指针快 2 倍，所以Df = 2 * Ds

使用 Df 和 Ds 之间的关系，并从上面放置值

N + Y = 2 * ( C + Y )

N + Y = 2*C + 2*Y

N = 2*C + Y

使用 N 的另一个关系，

C + Y + K = 2*C + Y

K = C

由此得出结论，头部与循环起点之间的距离等于汇合点节点与循环起点之间的距离。

尝试理解这一点，并始终尝试通过将任务分解成更小的块来简化任务。

希望这会有所帮助。

不断询问，不断成长：）

于 2018-07-27T11:03:28.690 回答
0

这就是你所缺少的。

每当两个指针都在循环中并且快速指针是循环长度的倍数时，快速指针已经与慢速指针重叠了整数次并且它们在同一个位置。如果您继续，它们会分开并再次圈。然后再次。然后再次。

该算法起作用的全部原因是这种研磨行为。

他们第一次见面时，可能是周期长度的严格倍数。例如，如果您有一个由 24 个节点组成的链导致一个长度为 7 的循环，那么它们将在 28 个步骤后首先相遇。

编辑 我在解释循环检测是如何工作的，而不是头部检测是如何工作的。这是对此的另一种解释。用不同的话来说。

假设我们有一个i节点链导致一个长度的循环j。我们最初运行快+慢指针并且它们相遇。为了满足，快的必须比慢的绕循环多走整数倍。所以他们在k*j几步之后相遇。

此时，慢速指针总共移动k*j了步数，其中i步数到达了循环，所以它已经k*j-i在循环内移动了步数。

现在我们将快速指针放在开头，并以相同的速度前进。在另一个i步骤中，开始处的指针已到达循环。与此同时，慢速指针之前已经在循环内移动了几步k*j-i，现在又在循环内移动了几步。由于是循环长度的倍数，所以也回到了起点，再次相遇。ik*jk*j

于 2018-05-29T22:58:12.020 回答