Pecobians.com :: Find the loop

poltergiest · 26 Sep 2005

Hi guys, it has been long time i have posted here but i m back

Now quest is : there is a list in which after node 7 the next link goes to third node instead 8th node how can we know there is a loop in the list.

We can not modify the data structure of the nodes

Struct node
{
int data;
struct node *next;
};

shantanu · 11 Feb 2005

Although there are many ways to do this, one efficient way could be:
Take 2 pointers and start hopping thru the list. One pointer traverses at a rate of 1(->next) and other traverses at a rate of 2(->next->next). If at any time the two pointers become equal, the list has a loop otherwise if anyone reaches null, it doesnt have a loop

Whacko · 09 Jul 2005

I'm not sure about this method but maybe somone can just tell me that am i wrong or right.Well the method is

take a temporary pointer n each time assign it the value of next pointer.but before this step first compare the value of next next pointer with the 1 stored in temp.If next pointer value is less then there is a probability of loop.we can store the initial address somewher .Although not lookin too efficient to me.