在单个链表中查找循环

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

从tortoise1和hare2开始,它们采用以下值:

(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,那就意味着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).

如果您需要更正式的证据,可以检查以下资源:

• 我们姐妹网站上的一个问题 ;
• 在维基百科的周期检测页面; 要么
• 2016年4月17日Peter Gammie撰写的"乌龟和野兔算法".

如果您只是支持该方法(非正式证明),您可以运行以下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

Answer 2

所选答案给出O(n*n)解决方案以找到循环的起始节点.这是一个O(n)解决方案:

一旦我们发现在周期慢A和快速乙相遇,让其中一人还是和其他的继续走,每次一步,决定周期中,周长说,P.

然后我们将一个节点放在头部,让它走P步,然后将另一个节点放在头部.我们每次将这两个节点前进一步,当它们第一次相遇时,它就是循环的起点.

Answer 3

您也可以使用哈希映射来查找链接列表是否有循环,函数使用哈希映射来查找链接列表是否有循环

    static bool isListHaveALoopUsingHashMap(Link *headLink) {

        map<Link*, int> tempMap;
        Link * temp;
        temp = headLink;
        while (temp->next != NULL) {
            if (tempMap.find(temp) == tempMap.end()) {
                tempMap[temp] = 1;
            } else {
                return 0;
            }
            temp = temp->next;
        }
        return 1;
    }

两种指针方法是最好的方法,因为时间复杂度是O(n)Hash Map所需的额外O(n)空间复杂度.