2

我了解 Floyd 循环检测算法的概念。得出的结论是，如果乌龟的行进速度是兔子的两倍，并且如果乌龟在一个循环中领先 k 米，那么乌龟和兔子将在循环之前遇到 k 米。

在单链表的情况下，指针 A 的移动速度是指针 B 的两倍。这意味着如果指针 B 需要 k 步才能到达循环的入口点（我们还不知道它在哪里），指针A 在循环内已经有 k 个节点的领先优势。因此，两个指针将在循环的入口点之前遇到 k 个节点。因此，如果我们将指针 B 移回头指针并将指针 A 保持在交汇点（现在两个指针都离入口点有 k 个节点），并以相同的速度移动，它们将在入口点相遇循环。

您如何证明该算法将在以下边界情况下工作？

  1. 最后一个节点循环回头部的链表。在这种情况下，起始值 k 是多少？
  2. 一个超长的链表，1000个节点，最后有一个小循环，3个节点。指针 A 将领先 1000，这意味着当指针 B 到达循环的入口点时，A 已经循环了很多次。
  3. 如果有 1 个节点的循环怎么办？

这不是家庭作业。一位面试官告诉我，如果我有一个小循环，这个算法将无法工作。他没有解释原因。

4

3 回答 3

5

很明显，如果有一个指针，两个指针最终都会到达循环。让我们假设，循环的长度为 N。我们可以计算循环中的位置模 N。

现在说指针A在位置a，指针B在位置b。在 s 步之后，A 将在 a+2s mod N 处，B 将在 b+s mod N 处。对于要相遇的两个指针，我们必须有

a+2s = b+s (mod N)
a+s = b (mod N)
s = b - a (mod N)

因此，在 b - a (mod N) 步骤之后，两个指针将相遇。

于 2013-11-12T20:15:52.770 回答
3

考虑一下：在n移动之后，您可以确定两个指针都在循环中，或者其中一些指针已经结束。在接下来n的动作中，您可以确定 A 和 B 会在某个点相遇，因为循环的大小是 <=n并且随着每一步，它们之间的差异会减少 1。

于 2013-11-12T20:15:23.317 回答
2

当然，它适用于一个小循环。考虑两个节点的循环。那是：

A => B => C => B

所以龟兔赛跑从 A 开始。下表显示了会发生什么：

Tortoise  Hare
   A       A
   C       B
   C       C

当只有两个节点时，乌龟总是在它开始的地方结束。因此，当兔子每次移动一个节点并最终赶上时，乌龟将基本上保持静止。

顺便说一句，当您有一个只有一个节点的循环时，也会发生同样的事情。也就是说，当一个节点在自身上循环时。

亨利的回答给出了数学证明。

于 2013-11-12T21:58:01.880 回答