Why does Floyd’s Cycle detection algorithm work?

What is a Linked List Cycle?

LinkedList cycle

What is Floyd’s Cycle detection algorithm?

Why does Floyd’s Cycle Algorithm works?

Well then let’s prove it.
Let,
x
= Distance between the start of the Linked List and the start of the cycle.
y = Distance between the start of the cycle to the point where slowPointer and fastPointer first meet each other.l = Total distance of the cycle.Distance travelled by slowPointer on meeting fastPointer is
So,
x + f*l + y = 2(x + s*l + y)
Solving this, we get
x + y = f*l - 2s*l
We can say, f*l - 2s*l = (some integer) * l = k*l
So, x + y = kl, where k is an integer
=> x = kl - y

I would love to hear from you

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store