15

我知道为了检测链表中的循环，我可以使用 Hare and Tortoise 方法，该方法包含 2 个指针（慢指针和快指针）。但是，在阅读 wiki 和其他资源后，我不明白为什么保证两个指针会在 O(n) 时间复杂度内相遇。

4

4 回答 4

33

这是一个非正式证明的尝试。

循环的形状无关紧要。它可以有一个长尾巴，和一个朝向末端的循环，或者只是一个从头到尾没有尾巴的循环。不管周期的形状如何，有一点很清楚 - 乌龟指针无法赶上兔子指针。如果两者曾经相遇，兔子指针必须从后面赶上龟指针。

确定后，考虑两种可能性：

  1. 野兔指针比乌龟指针落后一步。
  2. 野兔指针比乌龟指针落后两步。

所有更大的距离最终都会减少到一两个。

假设乌龟指针总是先移动（也可以反过来），那么在第一种情况下，乌龟指针向前迈出一步。现在它们之间的距离为2。当野兔指针现在走2步时，它们将落在同一个节点上。为了更容易理解，这里说明了相同的内容。太多的文字可能会妨碍您。

♛ = 野兔
♙ = 乌龟
X = 两者相遇

..♛♙... #1 - 最初，兔子比乌龟落后一步。
..♛.♙.. #2 - 现在乌龟迈出了一步。现在野兔落后了两步。
....X.. #3 - 接下来，兔子走了两步，它们相遇了！

现在让我们考虑第二种情况，它们之间的距离为 2。慢速指针向前移动一步，它们之间的距离变为 3。接下来，快速指针向前移动两步，它们之间的距离减小到 1，这与第一个案例，我们已经证明他们将再一步相遇。再次，为了便于理解而进行了图示。

.♛.♙... #1 - 最初，兔子比乌龟落后两步。
.♛..♙.. #2 - 现在乌龟迈了一步，它们之间的距离变成了三步。
...♛♙.. #3 - 接下来，兔子采取两个步骤，这与之前的情况相同。

现在，关于为什么这个算法保证在 O(n) 内，使用我们已经确定的兔子会在乌龟前进之前遇到乌龟的东西。这意味着一旦两者都在循环内，在乌龟完成另一轮之前，它将遇到兔子，因为兔子的移动速度是兔子的两倍。在最坏的情况下，循环将是一个有 n 个节点的圆。乌龟只能在 n 步内完成一轮，而兔子可以在这段时间内完成两轮。即使兔子在第一轮错过了乌龟（它会），它肯定会在第二轮赶上乌龟。

于 2011-06-26T08:53:44.783 回答
3

让迭代器A和B逐个遍历列表。康迪尔存在一个循环。那么在A进入循环的那一刻，B就已经在里面的某个地方了。如果循环的长度为K，B则将围绕它进行]K/2[移动，因此在2*]K/2[迭代中我们最多会遇到B出现A在远处1: B->A或后面的情况2: B->.->A，并且这是B第 'th 回合。在此之后，很明显，他们将在1或2移动中相遇。因此，如果循环存在并从某个位置开始P，那么我们最多进行2*P + 2*]K/2[ + 2 = O(N)迭代。

于 2011-06-26T08:58:04.993 回答
0

这是龟兔算法的while循环：

    while tortoise:
        hare = hare.next
        tortoise = tortoise.next
        # if not hare, states that i have a single node.
        # hare.next means that we have a tail value. So we do not have a cycle
        if (not hare) or (not hare.next):
            return False
        else:
            hare = hare.next
        if tortoise == hare:
            return True

虽然 hare 向前移动了 2 步，这意味着它有可能在一个循环中一遍又一遍地循环，一遍又一遍地接触多个节点，但从技术上讲，这一切都是在一个while循环中发生的。

于 2021-11-03T00:11:48.473 回答
-1 
//if you just want to check if there is a loop

loop = false;
item = head-of-list; 
while (item != nil)
{
   if (item.next < 0) 
   {
      loop = true; 
      break; 
   }
   else
   {
      actual = item;
      item = item.next; 
      actual.next = actual.next * -1; 
   }
} 

return loop;
于 2013-08-19T15:58:47.927 回答