如何检测链表中的循环？

Question

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

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

每个节点都指向下一个节点,最后一个节点除外.假设列表有可能包含一个循环 - 即最终的节点,而不是具有空值,具有对列表中的一个节点的引用.

什么是最好的写作方式

boolean hasLoop(Node first)

true如果给定的Node是带循环的列表的第一个,它将返回,false否则？你怎么写,这需要一个恒定的空间和合理的时间？

这是一个循环列表的图片:

Answer 1

您可以使用Floyd的循环寻找算法,也称为乌龟和野兔算法.

我们的想法是对列表进行两次引用,并以不同的速度移动它们.按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;
    }
}

Answer 2

以下是快速/慢速解决方案的改进,可正确处理奇数长度列表并提高清晰度.

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Answer 3

对于Turtle和Rabbit的替代解决方案,并不像我暂时更改列表那样好:

我们的想法是走在列表中,并在您前进时将其反转.然后,当您第一次到达已经访问过的节点时,其下一个指针将指向"向后",从而导致迭代first再次继续,在此处终止.

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

测试代码:

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

Answer 4

比弗洛伊德的算法更好

理查德布伦特描述了另一种循环检测算法,它非常类似野兔和乌龟[弗洛伊德的循环],除了这里的慢节点不移动,但后来被"传送"到固定的快节点位置间隔.

可在此处获得描述:http://www.siafoo.net/algorithm/11 布伦特声称他的算法比Floyd的循环算法快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;
}

Answer 5

乌龟和野兔

看看Pollard的rho算法.这不是同一个问题,但也许你会理解它的逻辑,并将它应用于链表.

(如果你很懒,你可以查看周期检测 - 检查关于乌龟和野兔的部分.)

这只需要线性时间和2个额外指针.

在Java中:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(大多数解决方案不检查两者next和next.next空值.此外,由于乌龟总是落后,你不必检查它是否为空 - 野兔已经这样做了.)

Answer 6

在这种情况下，到处都有文本材料的负载。我只是想发布一个真正帮助我掌握概念的图表表示。

当快慢在 p 点相遇时，

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

慢速行驶的距离 = a+b

因为快比慢快2倍。所以a+2b+c = 2(a+b)，那么我们得到a=c。

因此，当另一个慢指针再次从head运行到 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;
}

Answer 7

用户unicornaddict上面有一个很好的算法,但遗憾的是它包含一个奇怪长度> = 3的非循环列表的错误.问题是fast可能会在列表结束之前"卡住",slow赶上它,并且(错误地)检测到循环.

这是修正后的算法.

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

Answer 8

算法

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

复杂

Time ~ O(n)
Space ~ O(n)

Answer 9

以下可能不是最好的方法 - 它是O(n ^ 2).但是,它应该有助于完成工作(最终).

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}