Series: Subject: Topic:
Question: 26 of 51

# Finding a 'circle' in a linked list

You have n numbrer Node objects - could be 1,000,000 for all you know. Each Node has a getNext() method that returns the next Node (a linked list).

But the chain of n number of Node objects linked together by the getNext() method, somewhere in the chain, points back to a Node earlier in the chain so if you keep calling getNext() to walk the chain you will never get to the last Node - it will loop forever.

What is the best way to determine if this linked list of Node objects has a 'circle' and extra points if you can tell where in the chain does it occur i.e. what is the Node that is returing an earlier Node in the chain?

Asked by: wcmaggot | Member Since Jun-2009 | Asked on: Jun 8th, 2009

View all questions by wcmaggot

doddaiah

Answered On : Jun 21st, 2009

Take two pointers P1 and P2.

Initially let P1 and P2 point to starting node (S) and set counter to zero.
increment the counter
then check
while(1) {

if p1 == p2 ->next
{
print the counter value this is the node where circle starts.
exit();
}

else {
increment the counter;
p1 = p2;
p2 = p2->next;
if ( S == p2 )
exit(); if Staring node is equal to P2 then we have reached end of list.
}

}

1 User has rated as useful.

kaushurtz

Answered On : Mar 2nd, 2010

There are many ways to find loops in linked list but the best one is known as tortoise and hare algorithm.
In this we take 2 nodes say slow and fast node. Then we move the slow node by one shift ie startNode.next and the fast node with 2 shifts and then compare both slow and fast node. If they come to be equal at any time while iteration then this indicates that the linked list has a loop.