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!
Master programming languages like JavaScript, Typescript, design materials about HTML, CSS and Algorithms, through expert tutorials, software development best practices, and hands-on coding challenges for web development, app creation, and code optimization. Stay ahead in tech with cutting-edge insights on frameworks like React and Node.js, debugging techniques, and the latest industry trends to boost your coding skills and career growth in software engineering. Join a thriving developer community exploring AI, machine learning, and cloud computing while preparing for coding interviews and building scalable, efficient software solutions.