How to detect a loop in a linked list?

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 theywill definitely meet.
• Else either ofthe 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;    }}

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}

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/11Brent 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;}