Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forumdisplay.php?f=20)
-   -   Loop in single linked list (http://www.go4expert.com/showthread.php?t=10413)

mr.anandc 6May2008 12:37
Loop in single linked list
 
How to find a loop in a single linked list? The loop can be to any node in the list i.e., last node of the list can loop back to any existing node in the list.

Thanks.

asadullah.ansari 6May2008 13:17
Re: Loop in single linked list
 
Take two pointer one pointing to head and increment it by one by one. and second pointer also point to head and increment it by two and check these two pointer for eqaulity. If equal then loop is there .

mr.anandc 6May2008 13:45
Re: Loop in single linked list
 
Thanks for the reply.

I haven't got the concept. Suppose if I have a linked list of 10 nodes and last node is pointing back to second node, how this procedure will find a loop.

Thanks.

asadullah.ansari 6May2008 14:12
Re: Loop in single linked list
 
Code:
Node *Isloop(Node *List)
{
  Node *ptr1=List, *ptr2=List,*ptr=NULL;
  while( (ptr1!=NULL) && (ptr2!=NULL))
  {
    if (ptr && (ptr1 == ptr2))
    {
      return ptr;
    }
    ptr = ptr1;
    ptr1=ptr1->next;
    ptr2=ptr2->next;
    if (ptr2)
    {
      ptr2=ptr2->next;
    }
  }
}

mr.anandc 6May2008 16:37
Re: Loop in single linked list
 
Thanks for the code.

Can please explain behavior of this for the above scenario I mentioned like, 10 nodes in the list and last node pointing back to 2nd node. In this case how the code will find the loop.

asadullah.ansari 6May2008 17:55
Re: Loop in single linked list
 
Quote:
Originally Posted by mr.anandc
Thanks for the code.

Can please explain behavior of this for the above scenario I mentioned like, 10 nodes in the list and last node pointing back to 2nd node. In this case how the code will find the loop.
ptr1 1 2 3 4 5 6 7 8 9 10
ptr2 1 3 5 7 9 2 4 6 8 10

So loop is there bcoz ptr1==ptr2.
Here 1 2 3 etc represent node1 node2 node3 etc

Now I think you can understand. If Any doubt ask me?

mr.anandc 7May2008 09:38
Re: Loop in single linked list
 
Great logic, now I understood. Thanks a lot.


All times are GMT +5.5. The time now is 21:27.