How to determine if a linked list has a cycle using only two memory locations.

Question

Does anyone know of an algorithm to find if a linked list loops on itself using only two variables to traverse the list. Say you have a linked list of objects, it doesn't matter what type of object. I have a pointer to the head of the linked list in one variable and I am only given one other variable to traverse the list with.

So my plan is to compare pointer values to see if any pointers are the same. The list is of finite size but may be huge. I can set both variable to the head and then traverse the list with the other variable, always checking if it is equal to the other variable, but, if I do hit a loop I will never get out of it. I'm thinking it has to do with different rates of traversing the list and comparing pointer values. Any thoughts?

Answer 1

You can use the Turtle and Rabbit algorithm.

Wikipedia has an explanation too, and they call it "Floyd's cycle-finding algorithm" or "Tortoise and hare"

Answer 2

Absolutely. One solution indeed can be traversing the list with both pointers, one travelling at twice the rate of the other.

Start with the 'slow' and the 'fast' pointer pointing to any location in the list. Run the traversal loop. If the 'fast' pointer at any time comes to coincide with the slow pointer, you have a circular linked list.

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

Answer 3

I would suggest using Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. It has O(n) complexity and I think it fits your requirements.

Example code:

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

More info on Wikipedia: Floyd's cycle-finding algorithm.

Answer 4

I tried to solve this myself and found a different (less efficient but still optimal) solution.

The idea is based on reversing a singly linked list in linear time. This can be done by doing two swaps at each step in iterating over the list. If q is the previous element (initially null) and p is the current, then swap(q,p->next) swap(p,q) will reverse the link and advance the two pointers at the same time. The swaps can be done using XOR to prevent having to use a third memory location.

If the list has a cycle then at one point during the iteration you will arrive at a node whose pointer has already been changed. You cannot know which node that is, but by continuing the iteration, swapping some elements twice, you arrive at the head of the list again.

By reversing the list twice, the list remains unchanged in result and you can tell if it had a cycle based on whether you arrived at the original head of the list or not.

Answer 5

Just wanted to give a comprehensive working program.

http://www.technicalypto.com/2010/01/java-program-to-find-loops-in-singly.html