This algorithm is also called Floyd algorithm or fast/slow pointer
It can be used to detect cycles in Linked List because eventually if there is a cycle, they will enter the cycle and loop there forever. They will reduce their distance as the hare moves faster and eventually meet
Array duplicates detection
Let:
- x be the distance to the cycle start
- y the distance from cycle start to first meeting point
- c the cycle length.
When they first meet:
- Tortoise has moved x + y
- Hare has moved x + y + nc (n is some integer)
Since Hare moves twice as fast as tortoise, we can then write:
2(x+y) = (x+y+nc)
=>
x = nc -y
We are looking for x
The interesting property is that:
- if we move tortoise from 0 for x, and hare for x, because x = nc -y, hare will perform nc cycles and walk backward -y step.
- Because it was at y within the cycle, it will now be at the beginning. That’s where they meet