如何检测链表中的循环?

2020年11月28日 67点热度 0条评论

假设您在Java中拥有一个链表结构。它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,但最后一个节点除外,后者的下一个为空。假设列表有可能包含一个循环-即最终的Node而不是null可能引用了列表中位于其之前的节点之一。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的Node是带有循环的列表的第一个,则返回
true,否则返回
false?您怎么写才能占用恒定的空间和合理的时间?

这是带有循环的列表的外观图:

解决方案如下:

您可以使用Floyd's cycle-finding algorithm,也称为草龟和野兔算法。
这个想法是有两个引用到列表,然后以不同的速度移动它们。向前移动一个1节点,另一个向前移动2节点。

  • 如果链表中有一个循环
    一定会见面的。
  • 其他之一
    两个引用(或它们的next)
    将成为null
  • 实现该算法的Java函数:

    boolean hasLoop(Node first) {
    
        if(first == null) // list does not exist..so no loop either
            return false;
    
        Node slow, fast; // create two references.
    
        slow = fast = first; // make both refer to the start of the list
    
        while(true) {
    
            slow = slow.next;          // 1 hop
    
            if(fast.next != null)
                fast = fast.next.next; // 2 hops
            else
                return false;          // next node null => no loop
    
            if(slow == null || fast == null) // if either hits null..no loop
                return false;
    
            if(slow == fast) // if the two ever meet...we must have a loop
                return true;
        }
    }