Cute algorithms dilemma: can you determine if a linked list loops back on itself or if it terminates using only two pointers?

The answer is deceptively simple. Set both pointers to the head of the list. Then, iterate through the list, advancing the first pointer two nodes for every one node you advance the second pointer. On each iteration, compare the pointers against each other and against null. The list loops if the pointers are ever equal; it does not loop if either of the pointers is ever null.

As an extra bonus, it's an O(n) algorithm.

Here's a rough sketch of a proof:

Assume that we have a list with transient(non-looping part) of length T>=0 and period(looping part) of length P>1. Send two pointers down the list. One will advance j1 nodes at a time, the other will advance j2!=j1 nodes at a time. So, at some smallest time t0, both pointers will be in the loop, if there is one. The position of a pointer at t0 will depend on T and j. For the moment lets just call the positions of our pointers at t0, x1 and x2. So, the positions of the pointers in the loop are given by:

(j1*t+x1) mod P and (j2*t+x2) mod P

For this technique to work, we need the positions to be equal at some time t>t0. So,

(j1*t+x1) = (j2*t+x2) mod P =>

(j1*t - j2*t + x1 - x2) = 0 mod P =>

((j1-j2)t+(x1-x2))/P = n for some integer n>0 =>

t = nP/(j1-j2) + (x1-x2)/(j1-j2).

So, if j1=2 and j2=1, as above, t is obviously an integer for any P and T, which was what we wanted.

At the risk of turning this in to a GTKY node, here it is (in C++):

node * first = FirstNode;
node * current = first;
if(current->next == NULL)
        cout << "There's only one item, idiot";
else
{
        bool Loops = false;
        while(current->next != NULL && current->next != first)
        {
                current = curent->next;
                if(current->next == first)
                        Loops = true;
        }

        if(Loops)
                cout << "Yep, it loops";
        else
                cout << "Nope, it don't loop";
}
Sorry, imago's writeup is the most correct one, he merely failed to explicitly state that you test rigorously against NULL to make sure neither pointer goes off the list. What we want is a robust function capable of determining if any node in the list points to any previous node in the list.

Therefore we will need two pointers that traverse the list at different periods, and we will constantly test them against each other and NULL.

Here is the function in C++. Assuming a node structure similar to this:

struct Node
{
    int value;
    Node *next;
};
This function will detect any looping that occurs anywhere in the list:

bool CheckForLoop(Node *head)
{
    Node *node1 = head, *node2 = head;
    bool result, flag = false;

    while(flag == false)
    {
        if(node1->next == NULL) { flag = true; result = false; }
            else node1 = node1->next;

        if(node2->next == NULL) { flag = true; result = false; }
            else node2 = node2->next;

        if(node2->next == NULL) { flag = true; result = false; }
        else node2 = node2->next;

        if(node1 == node2) { flag = true; result = true; }
    }
    return result;
}

This is a perfect example of a case where the common convention of only ever returning from one point in the function greatly complicates the code.

bool CheckForLoop(Node *head)
{
    Node *node1 = head, *node2 = head;

    while (node2 && node2->next)
    {
        node1 = node1->next;
        node2 = node2->next->next;

        if (node1 == node2)
            return true;
    }

    return false;
}

This is sufficient checking because:

  • node1 follows in the path of node2, so if node2 is valid, node1, which refers to an earlier element of the list than node2, must also be valid.
  • node1 will never be set to NULL because if the list only has one element, the loop will never execute, and if the list has 2 or more elements, node2 or node2->next will become NULL first.
  • If node2 is the last node in the list, then the while condition will evaluate to false.
  • If the node after node2 is the last node in the list, then node2 will be assigned a NULL reference. This will never be equal to node1 in the if condition, because node1 is never set to NULL.

A more intuitive, hand-wavy version of zra's proof:

It obviously works when there's no loop.

Now, assume the slow pointer enter the looping part. Since it's a loop, we can see it as the slower pointer being ahead by some number of links. Then the faster pointer will reduce this distance by 1 link each step, until they meet. (And this will clearly take no longer than one "lap".)

zra generalized this e.g. to other pointer increments.

Log in or register to write something here or to contact authors.