Why does Floyd’s Cycle detection algorithm work?

What is a Linked List Cycle?

LinkedList cycle

Code

What is Floyd’s Cycle detection algorithm?

Floyd’s Cycle detection algorithm is used to detect whether the linked list has a cycle in it and what is the starting point(green node in the above diagram) of the cycle.

Algorithm to find whether there is a cycle or not :

  1. Declare 2 nodes say slowPointer and fastPointer pointing to the linked list head.
  2. Move slowPointer by one node and fastPointer by 2 nodes till either of one reaches nil.
  3. If at any point in the above traversal, slowPointer and fastPointer are found to be pointing to the same node, which implies the list has a cycle

Algorithm to find the starting node of the cycle:

After figuring out whether there is a cycle or not perform the following steps

  1. Reset the slowPointer to point to the head of the linked list and keep the fastPointer at the intersected position.
  2. Move both the fastPointer and slowPointer pointers by one node.
  3. The point at which they will intersect is the starting of the cycle.

Why does Floyd’s Cycle Algorithm works?

But can we prove whether the algorithm will even work?

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

You can reach me for any query, feedback, or just want to have a discussion by the following channels:

--

--

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