Proof of detecting the start of cycle in linked list

Question

From several posts inside stackoverflow and outside, I have come to know how to detect cycles in a linked list, the length of a cycle. I also found the method on how to detect the start of the loop.

Here are the steps again for reference.

Detecting Loop:

Have two pointers, classically called hare and tortoise. Move hare by 2 steps and tortoise by 1. If they meet at some point, then there is surely a cycle and the meeting point is obviously inside the cycle.

Finding length of Loop:

Keep one pointer fixed at meeting point while increment the other until they are same again. Increment a counter as you go along and the counter value at meet will be the length of cycle.

Find the start of cycle

Take one pointer to start of the list and keep the other at the meeting point. Now increment both by one and the meet point is the start of loop. I verified the method using some cases on paper, but I don't understand why it should work.

Can someone, provide a mathematical proof as to why this method works?

Answer 1

You can make your 'Find the start of cycle' proof simpler if you don't use meeting point.
Let second pointer start not at the 'meeting point', but M steps ahead of first pointer. (Where M is the length of the loop.)

This way, proof is pretty obvious. When the first pointer reaches start of the loop, second will be exactly M steps ahead: also at the start of the loop.