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)