Floyd’s Cycle Detection algorithm

Given a linked list , our aim is to detect whether or not it contain a cycle. If it contain a cycle then we are required to find the start node of the cycle.

This can be solved using Floyd’s Cycle Detection algorithm

We keep 2 pointers slow and fast, slow moves 1 step and fast moves 2 steps at a time and in case of presence of a cycle both of them meets at a node , Now it is confirmed that there is a cycle if they meet at some node, but how could we find the start node of this cycle ??. For this, the slow or any of the 2 pointers are made to point the head node, then both of them moves one step at a time. The node at which they meet this time is the start node of the cycle .

Proof

Let the distance from head to node just before start of cycle be ’m’ nodes(or steps)

and let there are p nodes in the cycle and k be the node in the cycle (starting from start node of cycle) at which they meet

For fast pointer,

f (total distance traversed by fast)= m+c1*p+k

c1 is a constant

for slow pointer

s(total distance traversed slow )=m+c2*p+k

c2 is a constant

Also note that as fast is 2 times faster than slow f=2*s

implies

m= (c1-c2) p -k

= c*p -k

add p and subtract p

=c*p -p + p-k

m = z*p +p-k

let p-k =d

then m=zp + d

z is another contant

where d is distance form the first meeting node to the start node of the cycle

Hence the proof,

That is for the second time, if we move them one step at a time , with one pointer at head initially and other at the node , where they have first met, then they both meet at the start of the cycle next time.

Time : O(n)

Space :O(1)