How can we find the starting node of a loop in link list?

Question

According to the Floyd's cycle finding algorithm, the point where tortoise and hare meets explains the circular nature in the link list.

To find the starting node in the cycle we initialize tortoise pointer to head of the list and starts incrementing hare and tortoise pointer by one unit. The point where they meet denotes the starting node of the cycle.

Please tell me how it works for the given situation.

The link list flows as:

1->2->3->4->5->6->7->8->3

Answer 1

Let's see.

You position the hare and the tortoise at 1, and let them run, the hare twice as fast as the tortoise.

At the zeroth step, both are at 1. At the first step, the tortoise moves to 2 and the hare moves to 3, and so on.

1 1
2 3
3 5
4 7
5 3
6 5
7 7 

So the hare and the tortoise meet at 7.

Now place the tortoise at the beginning, and let them run again, now with the same speed.

1 7
2 8
3 3 

So they indeed have met at the first element of the cycle.

And that's how it works for the given situation.