linked-list - 在单链表中查找循环

Question

如何检测单链表是否有循环？
如果它有循环，那么如何找到循环的起点，即循环开始的节点。

Answer 1

你可以通过简单地在列表中运行两个指针来检测它，这个过程在同名寓言之后被称为龟兔赛跑算法:

首先，检查列表是否为空( head 是 null )。如果是这样，则不存在循环，因此现在停止。

否则，启动第一个指针 tortoise在第一个节点 head ，和第二个指针 hare在第二个节点 head.next .

然后不断循环直到hare是 null (这在单元素列表中可能已经成立)，前进 tortoise通过一和hare每次迭代两个。兔子保证先到达终点(如果有终点)，因为它先开始并且跑得更快。

如果没有尽头(即，如果有一个循环)，它们最终将指向同一个节点，你可以停下来，知道你在循环中的某个地方找到了一个节点。

考虑以下从 3 开始的循环:

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6

开始 tortoise在 1 和 hare在 2 处，它们采用以下值:

(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)

因为它们在 (6,6) 处变得相等，以及自 hare应该总是超出 tortoise在非循环列表中，这意味着您发现了一个循环。

伪代码将是这样的:

def hasLoop (head):
  return false if head = null           # Empty list has no loop.

  tortoise = head                       # tortoise initially first element.
  hare = tortoise.next                  # Set hare to second element.

  while hare != null:                   # Go until hare reaches end.
    return false if hare.next = null    # Check enough left for hare move.
    hare = hare.next.next               # Move hare forward two.

    tortoise = tortoise.next            # Move tortoise forward one.

    return true if hare = tortoise      # Same means loop found.
  endwhile

  return false                          # Loop exit means no loop.
enddef

该算法的时间复杂度为 O(n)因为(乌龟和兔子)访问的节点数与节点数成正比。

一旦你知道循环中的一个节点，还有一个 O(n)保证找到循环开始的方法。

在循环中的某处找到元素后，让我们返回到原始位置，但您不确定循环的起点在哪里。

head -> 1 -> 2 -> 3 -> 4 -> 5
                  ^         |
                  |         V
                  8 <- 7 <- 6
                             \
                              x (where hare and tortoise met).

这是要遵循的过程:

提前hare并设置 size至 1 .

那么，只要hare和 tortoise不一样，继续前进hare , 增加 size每一次。这最终给出了循环的大小，在本例中为 6。

此时，如果size是 1 ，这意味着您必须已经处于循环的开始(在大小为 1 的循环中，只有一个可能的节点可以在循环中，因此它必须是第一个)。在这种情况下，您只需返回 hare作为开始，并跳过下面的其余步骤。

否则，同时设置 hare和 tortoise到列表的第一个元素并前进 hare正好size次(在本例中为 7)。这给出了两个完全不同的指针，它们的大小正好是循环的大小。

那么，只要hare和 tortoise是不同的，将它们一起推进(兔子以更稳重的速度奔跑，与乌龟的速度相同 - 我猜它从第一次跑就累了)。因为它们将保持原样 size元素始终彼此分开，tortoise将在与 hare 完全相同的时间到达循环的开始回到循环的开始。

您可以通过以下演练看到这一点:

size  tortoise  hare  comment
----  --------  ----  -------
   6         1     1  initial state
                   7  advance hare by six
             2     8  1/7 different, so advance both together
             3     3  2/8 different, so advance both together
                      3/3 same, so exit loop

因此 3是循环的起点，因为这两个操作(循环检测和循环开始发现)都是 O(n)并按顺序执行，整个事情加起来也是 O(n) .

如果您想要更正式的证明这是有效的，您可以查看以下资源:

question在我们的姐妹网站上；

Wikipedia cycle detection页;或

“龟兔赛跑算法”作者 Peter Gammie，2016 年 4 月 17 日。

如果您只是在支持该方法(不是正式证明)，您可以运行以下 Python 3 程序，该程序评估其对大量尺寸(循环中有多少元素)和导入(在循环开始)。

你会发现它总能找到两个指针相交的点:

def nextp(p, ld, sz):
    if p == ld + sz:
        return ld
    return p + 1

for size in range(1,1001):
    for lead in range(1001):
        p1 = 0
        p2 = 0
        while True:
            p1 = nextp(p1, lead, size)
            p2 = nextp(nextp(p2, lead, size), lead, size)
            if p1 == p2:
                print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
                break