2 Mar 2025

Turtle and Hare Algorithm: Cycle Detection with Examples and Use Cases

The Turtle and Hare algorithm (also known as Floyd's Cycle Detection Algorithm) is a classic two-pointer technique used to detect cycles in sequences like linked lists. In this post, we’ll break down how the algorithm works, provide step-by-step examples, explore real-world use cases, and even show you how to implement it in code.

What is the Turtle and Hare Algorithm?

This algorithm uses two pointers

Turtle (Slow Pointer): Moves one node at a time.
Hare (Fast Pointer): Moves two nodes at a time.

If a cycle exists in the linked list, the hare will eventually lap the turtle, and they’ll meet at a common node. If no cycle exists, the hare will reach the end of the list.

How Does the Turtle and Hare Algorithm Work?

Phase 1: Cycle Detection

Initialize both pointers at the head of the list.
Advance the turtle by 1 node and the hare by 2 nodes in each iteration.
If the hare reaches null, there’s no cycle.
If the hare and turtle meet, a cycle exists.

Phase 2: Finding the Cycle’s Start Node

Reset the turtle to the head of the list.
Advance both the turtle and hare by 1 node per iteration.
The node where they meet again is the cycle’s starting point.

Why It Works: When the two pointers meet inside the cycle, the distance from the head to the cycle’s start equals the distance from the meeting point to the start (mathematically proven).

Step-by-Step Example

Consider a linked list with a cycle: 1 → 2 → 3 → 4 → 5 → 3 (node 5 points back to node 3).

Initialization

Turtle (T) and Hare (H) start at node 1.

Iterations

T moves to 2; H moves to 3.
T moves to 3; H moves to 5.
T moves to 4; H moves to 3.
T moves to 5; H moves to 5.
Meeting at node 5: Cycle detected!

Find Cycle Start

Reset T to head (node 1).
Move T and H one step each until they meet again at node 3.
T moves to 4; H moves to 3.

Use Cases of the Turtle and Hare Algorithm

Linked List Cycle Detection

Detect infinite loops in linked structures.

Finding Duplicates in Arrays

Solve problems like 'LeetCode 287: Find the Duplicate Number' by treating the array as a linked list.

Polling Mechanisms

Prevent infinite loops in resource allocation or task schedulers.

Graph Theory

Detect cycles in graphs (requires adaptation for non-linear structures).

const findDuplicate = function(nums) {
  let tort = nums[0]
  let hare = nums[tort]
  while (tort !== hare){
    tort = nums[tort]
    hare = nums[nums[hare]]
  }
  
  tort = 0
  while (tort !== hare){
    tort = nums[tort]
    hare = nums[hare]
  }
  return hare
}

Conclusion

The Turtle and Hare algorithm is a powerful tool for detecting cycles efficiently (O(n) time, O(1) space). Whether you’re solving coding interview questions or optimizing resource management systems, understanding this algorithm is a must. Try implementing it yourself or adapting it to solve problems like finding duplicates in arrays!