Algorithm Spotlight: Floyd’s Cycle Detection Algorithm

Learn about Floyd’s Cycle Detection Algorithm!

Aaron M
4 min readSep 19, 2020

Last Updated: March 8, 2021

Welcome to the second week of Algorithm Spotlight! This week our featured algorithm is…drum roll please…Floyd’s Cycle Detection Algorithm!

Source

Right before we begin, if you missed out on the previous episode, here’s the Euclidean Algorithm article:

The Problem Statement

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where the tail connects to. If pos == -1, then there is no cycle in the linked list.

Want to read this story later? Save it in Journal.

Example 1:

Source: Linked List Cycle (LeetCode)
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Idea 1: Use a Set

The naive way of solving a cycle detection problem like this can be solved easily with a set:

Idea 2: Floyd’s Cycle Detection Algorithm

The first approach was a great idea, except it isn’t very smart. Let’s try to improve the code with Floyd’s Cycle Detection Algorithm.

The idea behind Floyd’s Cycle Detection Algorithm is where there are two pointers - a fast pointer (“hare”) and a slow pointer (“tortoise”). The slow pointer moves one step at a time, while the fast pointer moves two steps. Both pointers will move around the (possibly cyclic) list. If the list is not cyclic, both pointers will never contain the same data. If the list is cyclic, sooner or later, both pointers will meet. (see below for proof)

Now let’s prove that Floyd’s Cycle Detection Algorithm works mathematically. We can set the distance from the beginning to the start of the cycle to be x, the distance from the start of the cycle to the first place where the fast and slow pointer meets y, and the distance from y to the start of the cycle z.

Now we have our variables, we can define how many steps the fast and slow pointer moves:

fast pointer: x + 2y + z

slow pointer: x + y + z

Want to see the proof that the two pointers will meet? Check it out: https://math.stackexchange.com/questions/913499/proof-of-floyd-cycle-chasing-tortoise-and-hare/913529#913529.

Now that you have a solid understanding of Floyd’s Cycle Detection Algorithm, let’s implement it!

Implementing Floyd’s Cycle Detection Algorithm

Great work! Now onto some fun practice problems!

Problems

As always, practice makes perfect, so here are some sample problems for you to practice. Good luck!

Hints:

  1. We can break this problem down into two steps:
  • Finding if there is a cycle in the linked list
  • If there is a cycle, find the node where the cycle begins

Hints:

  1. The idea here is the same as Linked List II, except for this is an array, not a linked list.

Hints:

  1. At each step, perform the operation described, then check if the operations performed so far is a cycle.

Thanks for reading! Don’t miss out on the next episode of Algorithm Spotlight!

--

--

Aaron M
Aaron M

Written by Aaron M

Planet Earth, The Milky Way, Local Group, Virgo Supercluster, Laniakea Supercluster, the Universe

Responses (1)