在单链表中查找循环 [英] Finding loop in a singly linked-list

问题描述

如何检测单个链表是否存在循环? 如果它具有回路，那么如何找到回路的起点，即回路从其开始的节点.

解决方案

您可以通过在列表中运行两个指针来检测它，这一过程被称为寓言之后的乌龟和野兔算法相同的名字:

• 首先，检查列表是否为空(head为null).如果是这样，则不存在任何循环，请立即停止.
• 否则，在第一个节点head上启动第一个指针tortoise，在第二个节点head.next上启动第二个指针hare.
• 然后连续循环，直到hare为null(在一个元素列表中可能已经为真)，在每次迭代中将tortoise前进1并将hare前进2.由于野兔从头开始并且跑得更快，所以保证它首先到达末尾(如果是结束).
• 如果没有尽头(例如，有一个循环)，它们最终将指向相同的节点，并且您可以停止，只要知道您在循环中的某个位置某处即可.

考虑以下以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)保证方法可以找到循环的 start .

在循环中的某个位置找到元素后，让我们返回到原始位置，但是不确定循环的起始位置.

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

这是要遵循的过程:

• 前进hare并将size设置为1.
• 然后，只要hare和tortoise是不同的，继续前进hare，每次增加size.这最终给出了循环的大小，在这种情况下为六个.
• 在这一点上，如果size为1，则意味着您必须已经在循环的开始(在一个大小为1的循环中，只有一个可能的节点可以在周期中成为，因此必须 成为第一个).在这种情况下，您只需返回hare作为开始，然后跳过下面的其余步骤.
• 否则，将hare和tortoise都设置为列表的 first 元素，并将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).

---

如果您希望获得更正式的证明，那么您可以检查以下资源:

在我们姐妹网站上的
• a个问题；
• 维基百科周期检测页面；或
• 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

How can I detect that whether a singly linked-list has loop or not?? If it has loop then how to find the point of origination of the loop i.e. the node from which the loop has started.

解决方案

You can detect it by simply running two pointers through the list, this process is known as the tortoise and hare algorithm after the fable of the same name:

• First off, check if the list is empty (head is null). If so, no cycle exists, so stop now.
• Otherwise, start the first pointer tortoise on the first node head, and the second pointer hare on the second node head.next.
• Then loop continuously until hare is null (which may be already true in a one-element list), advancing tortoise by one and hare by two in each iteration. The hare is guaranteed to reach the end first (if there is an end) since it started ahead and runs faster.
• If there is no end (i.e., if there is a cycle), they will eventually point to the same node and you can stop, knowing you have found a node somewhere within the cycle.

Consider the following loop which starts at 3:

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

Starting tortoise at 1 and hare at 2, they take on the following values:

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

Because they become equal at (6,6), and since hare should always be beyond tortoise in a non-looping list, it means you've discovered a cycle.

The pseudo-code will go something like this:

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

The time complexity for this algorithm is O(n) since the number of nodes visited (by tortoise and hare) is proportional to the number of nodes.

---

Once you know a node within the loop, there's also an O(n) guaranteed method to find the start of the loop.

Let's return to the original position after you've found an element somewhere in the loop but you're not sure where the start of the loop is.

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

This is the process to follow:

• Advance hare and set size to 1.
• Then, as long as hare and tortoise are different, continue to advance hare, increasing size each time. This eventually gives the size of the cycle, six in this case.
• At this point, if size is 1, that means you must already be at the start of the cycle (in a cycle of size one, there is only one possible node that can be in the cycle so it must be the first one). In this case, you simply return hare as the start, and skip the rest of the steps below.
• Otherwise, set both hare and tortoise to the first element of the list and advance hare exactly size times (to the 7 in this case). This gives two pointers that are different by exactly the size of the cycle.
• Then, as long as hare and tortoise are different, advance them both together (with the hare running at a more sedate pace, the same speed as the tortoise - I guess it's tired from its first run). Since they will remain exactly size elements apart from each other at all times, tortoise will reach the start of the cycle at exactly the same time as hare returns to the start of the cycle.

You can see that with the following walkthrough:

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

Hence 3 is the start point of the cycle and, since both those operations (the cycle detection and cycle start discovery) are O(n) and performed sequentially, the whole thing taken together is also O(n).

---

If you want a more formal proof that this works, you can examine the following resources:

• a question on our sister site;
• the Wikipedia cycle detection page; or
• "The Tortoise and the Hare Algorithm" by Peter Gammie, April 17, 2016.

If you're simply after support for the method (not formal proof), you can run the following Python 3 program which evaluates its workability for a large number of sizes (how many elements in the cycle) and lead-ins (elements before the cycle start).

You'll find it always finds a point where the two pointers meet:

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

这篇关于在单链表中查找循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！