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

Question

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

Answer 1

只需在列表中运行两个指针就可以检测到它，这个过程在同名寓言之后被称为龟兔算法：
首先，检查列表是否为空（head是null）。如果是这样，没有循环存在，所以现在停止。
否则，在第一个节点上启动第一个指针tortoise，在第二个节点上启动第二个指针head。
然后继续循环，直到hare是head.next（这在一个元素列表中可能已经是正确的），在每次迭代中将hare前进一次，并将null前进两次。兔子保证先到达终点（如果有终点的话），因为它从前面开始跑得更快。
如果没有结束（即，如果有一个循环），它们最终将指向同一个节点，并且您可以停止，因为您知道您在循环中的某个地方找到了一个节点。
考虑以下从tortoise开始的循环：

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

从1的 hare开始，到2的 3开始，它们具有以下值：

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

因为它们在 tortoise处变得相等，并且由于在非循环列表中 hare应该始终在 (6,6)之外，这意味着您发现了一个循环。
伪代码将如下：

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

该算法的时间复杂度为 hare，因为被访问的节点的数量（由龟和兔）与节点的数量成正比。
一旦你知道了循环中的一个节点，还有一个 tortoise保证的方法可以找到循环的开始。
在循环中找到某个元素后，让我们返回到原始位置，但您不确定循环的起点在哪里。

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

这是要遵循的过程：
前进 O(n)并将 O(n)设置为 hare。
然后，只要 size和 1不同，继续前进 hare，每次都增加 tortoise这最终给出了循环的大小，在本例中是6。
此时，如果 hare是 size，则意味着您必须已经在循环的开始处（在大小为1的循环中，只有一个可能的节点可以在循环中，因此它必须是第一个节点）在本例中，您只需返回 size作为开始，并跳过下面的其余步骤。
否则，将 1和 hare都设置为列表的第一个元素，并精确地推进 hare次（在本例中为 tortoise）这给出了两个指针，它们与循环的大小完全不同。
然后，只要 hare和 size是不同的，就把它们一起推进（兔子以更平稳的速度奔跑，和乌龟一样的速度——我猜它第一次奔跑就累了）。由于它们将始终彼此保持完全的 7元素，因此 hare将在 tortoise返回循环开始的同时到达循环开始。
通过以下演练可以看到这一点：

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

因此 size是循环的起点，并且由于这两个操作（循环检测和循环开始发现）都是 tortoise并按顺序执行，因此将所有操作放在一起也就是 hare。
如果您想要更正式的证据来证明这一点，可以查看以下资源：
a 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