2- How to detect the starting point of the loop in Question-1 ?

2-Ans- First, detect if there is any loop using the approach described in Question-1. Once the loop is detected, then, reset pointer p1 so that it again points the starting node of the linked list, meanwhile do not change the position of pointer p2 . After that run a loop and for each iteration move both p1 and p2 with the same speed, ie. move them one node per iteration. After some time they will collide again and this collision point would be the starting point of the loop.

Proof - The above picture ( Fig -2.1 ) shows a snap shot at that moment when p1 has collided with p2 at node N _p as a result of the previous algorithm ( Question - 1 ).

Now, suppose the length between the starting node N ₀ and the junction node N _i is s , and the total length of the loop / circle is c . And ( see Fig-2.1 ) the distance from N _i to N _p is h and the distance from N _p to N _i is ( c – h ) [distances are measured in the direction of their movement].

By this time p2 might have taken r complete rotations (or may not ), thus we can safely say the number of rotations already taken by p2 within this loop is r >= 0 . Note, that p1 has not taken any full rotation of the loop, because when p1 was at N _i and p2 was at N _k , their distance was d < c ( see Fig-1.1 ), and they only had to reduce this distance to zero to collide – hence p1 could not take any full rotation within the loop.

Therefore, at the moment of collision while detecting the existence of the loop, p1 has travelled the distance ( s + h ), and p2 has travelled the distance ( s + r*c + h ), where as earlier stated r >= 0 .

As we know that the speed of p2 is double of p1 , we can write:

2*( s + h ) = (s + r*c + h);

Or, s + h = r*c ;

Hence, we can say that from now onwards if both p1 and p2 moves together at the same speed (one node at a time), then by the time p1 will cover distance s , p2 will cover ( r - 1 ) full rotations and ( c – h ) length more, ie. [ ( r - 1) full rotations + h less than another full rotation ].

Thus, now if we set p1 back to N ₀ ,and allow both p1 and p2 to move one node per iteration they will collide at N_i , which is the starting node of that loop !!