How to detect a loop in a linked list?

问题:

Say you have a linked list structure in Java. It\'s made up of Nodes:

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

and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.

What\'s the best way of writing

boolean hasLoop(Node first)

which would return true if the given Node is the first of a list with a loop, and false otherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?

Here\'s a picture of what a list with a loop looks like:

回答1:

You can make use of Floyd\'s cycle-finding algorithm, also known as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

• If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

Java function implementing the algorithm:

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;
    }
}

回答2:

Here\'s a refinement of the Fast/Slow solution, which correctly handles odd length lists and improves clarity.

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
}

回答3:

An alternative solution to the Turtle and Rabbit, not quite as nice, as I temporarily change the list:

The idea is to walk the list, and reverse it as you go. Then, when you first reach a node that has already been visited, its next pointer will point \"backwards\", causing the iteration to proceed towards first again, where it terminates.

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;

Test code:

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);
}

回答4:

Better than Floyd\'s algorithm

Richard Brent described an alternative cycle detection algorithm, which is pretty much like the hare and the tortoise [Floyd\'s cycle] except that, the slow node here doesn\'t move, but is later \"teleported\" to the position of the fast node at fixed intervals.

The description is available here : http://www.siafoo.net/algorithm/11 Brent claims that his algorithm is 24 to 36 % faster than the Floyd\'s cycle algorithm. O(n) time complexity, O(1) space complexity.

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;
}

回答5:

Tortoise and hare

Take a look at Pollard\'s rho algorithm. It\'s not quite the same problem, but maybe you\'ll understand the logic from it, and apply it for linked lists.

(if you\'re lazy, you can just check out cycle detection -- check the part about the tortoise and hare.)

This only requires linear time, and 2 extra pointers.

In 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;
}

(Most of the solution do not check for both next and next.next for nulls. Also, since the turtle is always behind, you don\'t have to check it for null -- the hare did that already.)

回答6:

The user unicornaddict has a nice algorithm above, but unfortunately it contains a bug for non-loopy lists of odd length >= 3. The problem is that fast can get \"stuck\" just before the end of the list, slow catches up to it, and a loop is (wrongly) detected.

Here\'s the corrected algorithm.

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;
    }
}

回答7:

Algorithm

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;
}

Complexity

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

回答8:

The following may not be the best method--it is O(n^2). However, it should serve to get the job done (eventually).

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++;
}

回答9:

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

Forgive me my ignorance (I\'m still fairly new to Java and programming), but why wouldn\'t the above work?

I guess this doesn\'t solve the constant space issue... but it does at least get there in a reasonable time, correct? It will only take the space of the linked list plus the space of a set with n elements (where n is the number of elements in the linked list, or the number of elements until it reaches a loop). And for time, worst-case analysis, I think, would suggest O(nlog(n)). SortedSet look-ups for contains() are log(n) (check the javadoc, but I\'m pretty sure TreeSet\'s underlying structure is TreeMap, whose in turn is a red-black tree), and in the worst case (no loops, or loop at very end), it will have to do n look-ups.

回答10:

If we\'re allowed to embed the class Node, I would solve the problem as I\'ve implemented it below. hasLoop() runs in O(n) time, and takes only the space of counter. Does this seem like an appropriate solution? Or is there a way to do it without embedding Node? (Obviously, in a real implementation there would be more methods, like RemoveNode(Node n), etc.)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error(\"must start with single node!\");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

回答11:

You could even do it in constant O(1) time (although it would not be very fast or efficient): There is a limited amount of nodes your computer\'s memory can hold, say N records. If you traverse more than N records, then you have a loop.

回答12:

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster\'s next
        // pointer is ever equal to slower then it\'s a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

回答13:

I cannot see any way of making this take a fixed amount of time or space, both will increase with the size of the list.

I would make use of an IdentityHashMap (given that there is not yet an IdentityHashSet) and store each Node into the map. Before a node is stored you would call containsKey on it. If the Node already exists you have a cycle.

ItentityHashMap uses == instead of .equals so that you are checking where the object is in memory rather than if it has the same contents.

回答14:

I might be terribly late and new to handle this thread. But still..

Why cant the address of the node and the \"next\" node pointed be stored in a table

If we could tabulate this way

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

Hence there is a cycle formed.

回答15:

Here is my runnable code.

What I have done is to reveres the linked list by using three temporary nodes (space complexity O(1)) that keep track of the links.

The interesting fact about doing it is to help detect the cycle in the linked list because as you go forward, you don\'t expect to go back to the starting point (root node) and one of the temporary nodes should go to null unless you have a cycle which means it points to the root node.

The time complexity of this algorithm is O(n) and space complexity is O(1).

Here is the class node for the linked list:

public class LinkedNode{
    public LinkedNode next;
}

Here is the main code with a simple test case of three nodes that the last node pointing to the second node:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

Here is the a simple test case of three nodes that the last node pointing to the second node:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

回答16:

This code is optimized and will produce result faster than with the one chosen as the best answer.This code saves from going into a very long process of chasing the forward and backward node pointer which will occur in the following case if we follow the \'best answer\' method.Look through the dry run of the following and you will realize what I am trying to say.Then look at the problem through the given method below and measure the no. of steps taken to find the answer.

1->2->9->3 ^--------^

Here is the code:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

回答17:

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Use above function to detect a loop in linkedlist in java.

回答18:

Detecting a loop in a linked list can be done in one of the simplest ways, which results in O(N) complexity.

As you traverse the list starting from head, create a sorted list of addresses. When you insert a new address, check if the address is already there in the sorted list, which takes O(logN) complexity.

回答19:

You may use Floyd\'s tortoise algorithm as suggested in above answers as well.

This algorithm can check if a singly linked list has a closed cycle. This can be achieved by iterating a list with two pointers that will move in different speed. In this way, if there is a cycle the two pointers will meet at some point in the future.

Please feel free to check out my blog post on the linked lists data structure, where I also included a code snippet with an implementation of the above-mentioned algorithm in java language.

Regards,

Andreas (@xnorcode)

回答20:

Here is the solution for detecting the cycle.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

回答21:

This approach has space overhead, but a simpler implementation:

Loop can be identified by storing nodes in a Map. And before putting the node; check if node already exists. If node already exists in the map then it means that Linked List has loop.

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;  
  }  

回答22:

Here is my solution in java

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

回答23:

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}