3

如何在给定的链表中找到循环的开始节点？让我们称之为循环点

到目前为止，我已经了解以下内容（使用慢/快指针）：

  1. 假设列表具有大小的非循环部分k
  2. 慢动作 k 步
  3. 快速移动 2k 步
  4. 快速是(2k - k)=k慢步ahead
  5. 慢是在循环的开始；也被称为Cycle point
  6. 快速是此时的(LOOP_LENGTH - k)步数或慢速指针behindCycle point
  7. 每走 1 步慢动作，快走 2 步，慢走 1 步。
  8. (LOOP_LENGTH - k)因此，遇到慢速和碰撞需要快速的步骤
  9. 这是我不明白的步骤： 在这个碰撞点，两个节点都k将从循环的前面开始。
  10. 一旦找到碰撞点，将一个指针移动到列表的头部。
  11. 现在以 1 步/转的速度移动两个指针直到发生碰撞。它们相遇的节点是循环的开始，因此Cycle point

有人可以解释一下第 9 步和之后的步骤吗？

谢谢

编辑：

我想指出的一件事是，一旦进入循环，快指针永远不会超过慢指针。他们会发生碰撞。原因如下：slow 在 i 处，fast 在 i-1 处假设。当它们移动时，slow=> i+1 和 fast 也将在 i+1，因此会发生碰撞。或者，慢在 i 处，快在 i-2 处。下一步，slow-> i+1；快：我。下一步，慢-> i+2，快：i+2，因此再次碰撞。这么快永远追不上慢，只能在循环内碰撞一次！

4

2 回答 2

3

你的6.错了，快指针离当时在循环点的慢指针还有k步；但最好使用before或behind而不是away。另外，k可能更小、更大或等于loop_length.

因此，k当到达循环点时，快速指针比慢速指针领先一步，在您的假设下，循环点k在开始后几步。现在，在循环上测量，快速指针k % loop_length比循环点提前几步。正确的？如果k = some_n * loop_length + r，则快速指针r比循环点超前一步，即r := k % loop_length超前一步。

但这意味着慢速指针在loop_length - r循环中领先于快速指针。毕竟这是一个循环。因此，在loop_length - r额外的步骤之后，快速指针将赶上慢速指针。对于每一步，慢速指针移开，快速指针靠近两步。

所以我们不知道k，我们不知道，loop_length或者r，我们只知道m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length。直到两个指针相遇点的总步数m是循环长度的倍数。

所以现在我们重新开始，在开始时有一个新的指针，在它遇到快的地方，慢，m领先于新的。我们以相同的速度移动新的和慢的，每次移动 1 步，并且在循环点它们会相遇 - 因为当新指针到达循环点时，第二个仍然m领先一步，也就是说，m % loop_length == 0沿着环路向前迈进。这样我们就可以知道什么k是（我们一直计算我们的步数）和循环点。

我们loop_length通过再循环一次来找到，直到两者再相遇一次。

于 2012-07-21T11:18:49.283 回答
0

嗯..除非您面对面交谈，否则这种问题很难解释。我会试一试。

首先在第6步：我认为快速指针应该k远离圆点。

但是留下这一切。我们现在有两辆车。快车的速度是慢车的两倍。

假设快车在k远离圆点的圆轨道上开始。

慢车从圆点开始。

现在我说两辆车将在k圆点之前的距离处相遇。

为什么？因为最初快车k距离圆点有一定距离。n第一次完成循环时，快车将覆盖距离。现在快车又在距离圆点 k 处。但慢车n/2距离圆点有一定距离。

现在，快车必须n-2k行驶更多k距离才能到达圆点之前的距离。慢车必须经过n/2 - k = (n-2k) / 2一段距离才能到达k起点之前的距离。Which is exactly half the distance of the path to be covered by the fast car. 快车的速度是慢车的两倍。

所以很明显他们会在k距离圆点之前的距离相遇。

于 2012-07-21T10:59:14.270 回答