Floyd’s Cycle Detection Algorithm

A pointer algorithm that uses two pointers at different speeds to travel through the sequence. It is used to determine whether the linked list has a cycle/loop or not. In this story, we will use this algorithm to detect cycle, find the length and the start node of the cycle and remove the cycle in the linked list.

Floyd’s Cycle Detection Algorithm summary card

Table of Contents
· How Does Floyd’s Cycle Detection Algorithm Work?
· Has Cycle
  ∘ Graphical Explanation
  ∘ Code Implementation
· Find the Length of Cycle
  ∘ Graphical Explanation
  ∘ Code Implementation
· Find the Start node of Cycle
  ∘ Graphical Explanation
  ∘ Code Implementation
· Remove the cycle
  ∘ Graphical Explanation
  ∘ Code Implementation

How Does Floyd’s Cycle Detection Algorithm Work?

Floyd’s Cycle Detection Algorithm initializes two pointers, fast and slow from the head of a linked list. The fast pointer moves at twice the speed of the slow pointer. That’s why this algorithm also known as Floyd’s Tortoise and Hair Algorithm. If there is a cycle/loop in the linked list, the two pointers will be bound to meet. Otherwise, the fast pointer will hit the end of the linked list.

Has Cycle

LeetCode 141: Linked List Cycle

Use two pointers, slow and fast. The fast pointer moves twice faster than the slow pointer.

fast = fast.next.next
slow = slow.next

If a cycle presents in the linked list, the fast pointer will move past the slow pointer at some point.

# fast pointer touches the slow pointer
fast == slow

Otherwise, the faster pointer reaches the tail of the linked list.

Graphical Explanation

• has cycle in the linked list

has cycle linked list

has cycle process

• has no cycle in the linked list

has no cycle linked list

has no cycle process

Code Implementation

• Complexity
  Time: O(n), traverse through the whole linked list
  Space: O(1), only two pointers are used
  n: the total number of nodes in the input linked list
• Golang

• Python

Find the Length of Cycle

After we found a cycle in the linked list, save the slow pointer. Then setup another pointer to iterate thought the whole cycle until it meets the slow pointer again.

Graphical Explanation

find cycle length process

Code Implementation

• Complexity
  Time: O(n)
  Space: O(1)
  n: the total number of nodes in the input linked list
• Golang

• Python

Find the Start node of Cycle

LeetCode 142: Linked List Cycle II

If a cycle is detected in the linked list, we move forward to trace the start node of the cycle.

Assume that the distance between the head of the linked list and the start node of the cycle is a , the distance between the cycle starting point to the meeting point where fast pointer touches the slow pointer is b . From the meeting point to the cycle staring point, the distance is c. The slow pointer traveled a + b distance and the fast pointer moved a + b + c + b length when they met each other. Since the fast pointer is two times faster than the slow pointer, the faster pointer traveled twice the distances the slow pointer traveled. Based on that, we get a = c .

distance relations

Therefore, reset the slow pointer to the head of the linked list and remain the fast pointer at the meeting point. Then move both pointers one step at a time until they collide at a node where the cycle starts in the linked list.

Graphical Explanation

find start node of cycle

Code Implementation

• Complexity
  Time: O(n)
  Space: O(1)
  n: the total number of nodes in the input linked list
• Golang

• Python

Remove the cycle

We have detected a cycle and found the starting node of the cycle in the linked list. In order to remove the cycle, we need to get the last node of the cycle and fix the next pointer of the last node to null.

Graphical Explanation

Code Implementation

• Complexity
  Time: O(n)
  Space: O(1)
  n: the total number of nodes in the input linked list
• Golang

• Python

You can access the source code here.

If you are interested in detect cycle in a graph, please check Detect Cycle in a Graph.

LeetCode Problems:

• LeetCode 141: Linked List Cycle
• LeetCode 142: Linked List Cycle II