Two Pointer in Linked List

Let's think of this case :

Suppose we have a Linked List and we need to check whether it has  Cycle or not.

Consider two pointers one is slow pointer and the other one is fast pointer.

So the slow pointer moves one step and the fast pointer moves in two steps .


Imagine two runners running on a circular track :

The fast runner eventually meets the slow runner some where on the track.

Exactly in the same manner :

1. If the fast pointer meets slow pointer it has Cycle.

2. If the fast pointer reaches the end of the linked list means it has no Cycle.


It is always safe that slow pointer moves one step at a time and fast pointer moves two steps at a time.

For each iteration the fast pointer will move one step ahead of the slow pointer and will meet slow pointer after m iterations.