1- How to test if a singly linked list has a loop in it ?

1-Ans- Get two pointers p1 and p2 pointing to the starting node of the linked list. Then run a loop and move p1 one node per iteration and p2 , two nodes per iteration, ie. p2 should move at a speed which is double of that of p1 . If there is no loop, p2 will reach up to the end of the linked list, ie. it will reach the node where the next node is NULL. Otherwise, p2 will collide with p1 at some point of time, ie. at some point of time they will point to the same node.

Proof - As p2 runs faster than p1, p2 will enter the loop first [if at all, there is a loop]. After that p2 will move within the loop and after some times p1 will also enter the loop. The above picture ( Fig -1.1 ) shows a snap shot at that moment when p1 has just entered the loop, ie. P1 is on the node N _i , where the loop starts, and at that moment p2 is somewhere within the loop at node N _k .

Now let us consider, at this moment, the distance between N _k and N _i to be d , ie. There are as many as d gaps (or d-1 nodes) between N _k and N _i . [Notice that the distance is measured in the same direction of movement].

For each iteration, p1 moves one node, and p2 moves two nodes ahead. That means the distance bwtween p1 and p2 reduces by 1 per iteration. Thus, definitely after d more iterations their distance will be zero , ie. they will collide. And this is only possible if there is a loop in the linked list. Otherwise, p2 will reach the last node earlier.