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

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

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

你可以使用弗洛伊德的周期寻找算法,也被称为乌龟和野兔算法。 其思想是对列表有两个引用,并以不同的速度移动它们。一个向前移动1个节点,另一个向前移动2个节点。

如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为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;
    }
}

其他回答

比弗洛伊德的算法好

Richard Brent描述了一种替代周期检测算法,它很像兔子和乌龟(弗洛伊德周期),除了这里的慢节点不移动,但随后会以固定的间隔“传送”到快节点的位置。

该描述可在布伦特的周期检测算法(瞬移海龟)。布伦特声称他的算法比弗洛伊德的循环算法快24%到36%。 O(n)时间复杂度,O(1)空间复杂度。

public static boolean hasLoop(Node root) {
    if (root == null) return false;
    
    Node slow = root, fast = root;
    int taken = 0, limit = 2;
    
    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if (slow == fast) return true;
        
        if (taken == limit) {
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

你也可以使用上述答案中所建议的弗洛伊德乌龟算法。

该算法可以检查单链表是否具有闭合循环。 这可以通过迭代带有两个移动速度不同的指针的列表来实现。通过这种方式,如果存在一个循环,两个指针将在未来的某个时间点相遇。

请随意查看我关于链表数据结构的博客文章,在那里我还包含了一个用java语言实现上述算法的代码片段。

问候,

安德烈亚斯 (@xnorcode)

这种方法有空间开销,但实现更简单:

循环可以通过在Map中存储节点来标识。在放置节点之前;检查节点是否已经存在。如果节点已经存在于映射中,则意味着链表有循环。

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }  

在这个上下文中,到处都有文本材料的加载。我只是想张贴一个图表表示,真正帮助我掌握概念。

当快、慢在点p相遇时,

快速行进的距离= a+b+c+b = a+2b+c

慢行距离= a+b

因为快的比慢的快2倍。 所以a+2b+c = 2(a+b)然后得到a=c。

因此,当另一个慢指针再次从头部运行到q时,同时,快速指针将从p运行到q,因此它们在q点会合。

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

你可以使用弗洛伊德的周期寻找算法,也被称为乌龟和野兔算法。 其思想是对列表有两个引用,并以不同的速度移动它们。一个向前移动1个节点,另一个向前移动2个节点。

如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为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;
    }
}