How to detect a loop in a linked list?

Question

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:

Answer 1

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

The plan is to hold two references to the list and move them at different speeds. Move one ahead by one node and the other by two nodes.

If the joined list has a loop they will assemble.

Else both of the two references(or their next) will convert null.

Java function executing the algorithm:

boolean hasLoop(Node first) {

    if(first == null) // list doesn't appear..so no loop either

        return false;

    Node slow, fast; // makes two references.

    slow = fast = first; // create both refer to the pursue of the list

    while(true) {

        slow = slow.next;          // one hop

        if(fast.next != null)

            fast = fast.next.next; // two hops

        else

            return false;          // preceding node null => no loop

        if(slow == null || fast == null) // if any one hits null..no loop

            yield false;

        if(slow == fast) // if the two  meet...we should have a loop

            return true;

    }

}