#floyds algorithm

This is a classic problem in Linked Lists. You are given a list which contains a cycle. One way of thinking about a cycle is this - the "last" node instead of pointing to NULL points to some previous element in the list thereby creating a cycle. 

The first task is to detect whether there is  a cycle. Class problems often have classic solutions. As does this one - the "Floyd's cycle-finding algorithm". 

You take a hare and a tortoise and the hare moves along twice as fast as the tortoise. So, for every one node move by the tortoise the hare jumps two. If either of them reach a NULL node there is no cycle, and if they meet then we have detected a cycle. 

So far so good, but now we have to find the start of the loop. Here is how we set up the problem. 

Node Position of the start the Loop = K (i.e. if you move K nodes from the head you will be at the start of the loop)

Size of the Loop = M (i.e. if you move M nodes from the start of the loop then we come back at the start of the loop)

Number of iterations when the hare and tortoise meet = I (i.e. the tortoise has moved I steps and the hare has moved 2I steps)

Tortoise's position from the loop start = (I - K) mod M

Hare's position from the loop start = (2I - K) mod M

Since they have met, we have 

(2I - K) mod M = (I-K) mod M

Now, simplifying this using simple modulo arithmetic we have 

[(2I -K) - (I-K) ] mod M = 0

this gives us,

I Mod M = 0 ( this makes intuitive sense, since the additional steps taken by the hare are a multiple of M i.e. the extra distance travelled by the hare is just a multiple of the size of the loop - so the hare and the tortoise are obviously at the same point)

Now let's change the rules of the hare and tortoise game.

We know that the tortoise it at the position (I-K) mod M. So, if it takes K more steps it will be at the position (I-K+K) mod M which is I mod M (this we know is 0 i.e. the loop start)

So now we send back the hare to the start of the loop and slow it down to one step per iteration and let the tortoise continue one step per iteration. 

In exactly K iterations the hare and tortoise will meet again, at the start of the loop. 

When they meet we have the Node that is the start of the loop. 

Source Code