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

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 2

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"