[algogeeks] Re: Length of Linked List with Cycle

[Vinodh Kumar]

To  find the length of the loop:

1)You know the node where the two pointers have met.(say NodeX)
2)Now make one pointer alone traverse through the loop.(Have a counter which increments for every move)
3)It will come back to the same node (NodeX) after making 'length of the loop' jumps
ie the counter gives  the length of the loop.

 To find the node where the loop starts.

1)You know  the length of the loop.
2)position  both the pointers to the beginning of the loop.
3)move one pointer alone  for the length of the loop.(ptr1)

[1]----->[2]----->[3]----->[4]----->[5]----->[6]----->[7]----->[8]------>[9]------>[10]
                                                                             ^                       |
                                                                             |                       v
                                                                          [13]<-----[12]<-----[11]


Here the length of the loop is 6.
First move one pointer ptr1 to the sixth node.
Now start the second pointer and move them parallely.
The point where they meet if the beginning of the loop.

 Logic :
 Let k be the portion of the list outside the loop.

Total length of the list is n + k ( n is the length of the loop).

The two pointers will meet after they have made k moves because ,  the first pointer (ptr1) would have travelled the length of the list(n initially and k now) , ie it would be coming into the loop  from the last element of the list while the pointer ptr2 would just be entering the loop.
Thus you can find the starting of the loop.

Hope  this helps
Vinodh



--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---