Algorithm Spotlight: Floyd’s Cycle Detection Algorithm
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!
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:
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:
- 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:
- The idea here is the same as Linked List II, except for this is an array, not a linked list.
Hints:
- At each step, perform the operation described, then check if the operations performed so far is a cycle.
