Pattern: Slow and Fast Pointers

It's a pointer algorithm that involves two pointers that move through the Array or LinkedList at different speeds. It's also known as Hare and Tortoise algorithm.

The algorithm proves that the two pointers are bound to meet in case there is a cycle in the LinkedList.

image.png

Imagine two racers running in a circular racing track. If one racer is faster than the other, the faster racer is bound to catch up and cross the slower racer from behind.

Many problems relating to LinkedLists can be solved using this technique, namely Finding the Middle Node in the LinkedList, LinkedList Cycle Detection, Find the length of the Cycle in a LinkedList etc.