Why does Floyd’s Cycle detection algorithm work?

What is a Linked List Cycle?

LinkedList cycle

Code

What is Floyd’s Cycle detection algorithm?

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:

  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?

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

--

--

--

Software Developer(iOS), Speaker & Writer at Swift India

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Visualising complex APIs using API Map

Azure MySQL with AAD and Managed Identity

Partition Labels LeetCode Solution

Partition Labels LeetCode Solution

Story of Unsuccessful PR to Open Source Project! ( Part 2 )

When Data meets Splunk

(SQLI) How I Hack Hundreds Of Students Data On Goverment Website

The Advantages of HyperDAO’s Flat Hierarchy

The CRUD’s Story

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
G. Abhisek

G. Abhisek

Software Developer(iOS), Speaker & Writer at Swift India

More from Medium

Android CI/CD pipeline with Github Actions: Demystifying Github Actions

[#WomenInTech] Journey from Software Development to DevOps

How to upload images to AWS S3 from the Android app.

Google Chrome Enterprise Empowering