在单链表中查找循环

Question

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

Answer 1

您还可以使用哈希映射来查找下面的链接列表是否有循环。函数使用哈希映射来查找链接列表是否有循环

    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）哈希映射所需的空间复杂度加上O（n）空间复杂度。

Answer 2

选择的答案给出了一个O（n*n）解，以找到循环的开始节点。这里有一个O（n）解：

一旦我们发现慢A和快B在循环中相遇，让其中一个静止不动，另一个每次继续走一步，以决定循环的周长，比如，P。

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

Answer 3

您只需在列表中运行两个指针就可以检测到它，这个过程被称为龟兔算法，其前身是同名寓言：

• 首先，检查列表是否为空（head为null）。如果是这样，就不存在循环，所以现在停止

考虑下面的循环，该循环从<代码> 3 /代码>开始：

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

从1开始的tortoise和从2开始的hare具有以下值：

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

因为它们在（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

该算法的时间复杂度为O（n），因为访问的节点数（龟兔）与节点数成正比。

一旦知道循环中的一个节点，还有一个O（n）方法可以找到循环的起点。

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

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

这是要遵循的过程：

• 前进hare并将size设置为1

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

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）。

如果您想要更正式的证据证明这一点，您可以查看以下资源：

• 关于我们姐妹网站的一个问题

如果您只是想获得对该方法的支持（不是形式证明），那么可以运行以下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