In last post, we found how to detect if there is a loop in singly link list or not. Now we will see how to detect where the loop starts.In above figure, we see that loop starts at node (a) after length x and loop length is z. So the total length of link list is (x+z). Also as we saw in last post that slow and fast iterator will meet at some node (b).
Please note if we move a pointer (one node per iteration) from (b) and keep count of nodes until we visit (b) again, we will be able to calculate z.
After finding z, start an iterator itr1 form head and move it z nodes from head at (c). Take another iterator itr2 and start it from head. Now if you move itr1 and itr2 in parallel one node at a time, they will meet first at start of the loop (a).
Explanation is based on following invariance:
"In a circle if we start from some point and move the distance equal to circumference along circle periphery, we will be at the same point again."
Both the iterators are meeting at (a) coz itr1 is z nodes ahead from itr2. Once itr1 is at (a), itr2 is z nodes behind (a). After z iterations, itr2 will reach (a) and itr1 also reaches (a) because of above invariant.
This solution has been suggested by Saket in comments to last post. Great solution Saket!
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.