Floyd's Cycle Detection (Tortoise and Hare)
An algorithm to detect cycles in a linked list using two pointers moving at different speeds. Invented by Robert Floyd, this elegant algorithm uses O(1) space compared to the hash set approach. Also known as the tortoise and hare algorithm, it's one of the most important linked list algorithms with applications beyond linked lists.
Visualization
Interactive visualization for Floyd's Cycle Detection (Tortoise and Hare)
Interactive visualization with step-by-step execution
Implementation
1class ListNode {
2 val: number;
3 next: ListNode | null = null;
4
5 constructor(val: number) {
6 this.val = val;
7 }
8}
9
10function hasCycle(head: ListNode | null): boolean {
11 if (!head || !head.next) return false;
12
13 let slow = head;
14 let fast = head;
15
16 while (fast && fast.next) {
17 slow = slow.next!;
18 fast = fast.next.next;
19
20 if (slow === fast) return true;
21 }
22
23 return false;
24}
25
26function detectCycleStart(head: ListNode | null): ListNode | null {
27 if (!head || !head.next) return null;
28
29 let slow = head;
30 let fast = head;
31
32 // Detect cycle
33 while (fast && fast.next) {
34 slow = slow.next!;
35 fast = fast.next.next;
36
37 if (slow === fast) {
38 // Cycle found, find start
39 slow = head;
40 while (slow !== fast) {
41 slow = slow.next!;
42 fast = fast!.next!;
43 }
44 return slow;
45 }
46 }
47
48 return null;
49}Deep Dive
Theoretical Foundation
Floyd's Cycle Detection uses two pointers moving at different speeds. The slow pointer (tortoise) moves one step at a time while the fast pointer (hare) moves two steps. If there's a cycle, the fast pointer will lap the slow pointer and they'll meet inside the cycle. Mathematical proof: in a cycle of length C, after meeting, the distance from head to cycle start equals the distance from meeting point to cycle start. This property allows finding the cycle start by resetting one pointer to head and moving both one step until they meet again. Time: O(n), Space: O(1). Works for detecting duplicates when array indices are used as 'next' pointers.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Detecting cycles in linked lists
Finding duplicate numbers (using index as next pointer)
Cycle detection in state machines
Pollard's rho algorithm for integer factorization
Memory leak detection
Detecting infinite loops in programs
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.