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

What not to do when using async background jobs(based on rails+sidekiq experience)

Time to archive Create-react-app

Configuring Development environment for Go-Lang in Windows 10

Track Flight Status, Schedules, and Routes of Caribbean Airlines with an API

Cost Optimization | AWS | Why, What, When, Who, How?

Observations about Web Service Technologies: Using Custom Web Clients

How to refactor GildedRose-Refactoring-Kata with Simple Factory Pattern and Strategy Pattern

HashQuark Monthly Staking Report | Oct 2020

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

Declarative approach in Mobile development

Increasing Efficiency in Mobile App Development

Collection of Data in Swift

Third-party apps — a small rant