Detect cycles, find midpoints, and solve linked list problems using two pointers moving at different speeds.
The Fast & Slow Pointers technique (also known as Floyd's Tortoise and Hare) uses two pointers that traverse a sequence at different speeds. Typically, the slow pointer moves 1 step at a time, while the fast pointer moves 2 steps at a time.
After 2 iterations: slow is at node 3 (moved 2), fast is at node 5 (moved 4). The fast pointer advances twice as quickly, which creates the mathematical properties we exploit.
Core principle: If there is a cycle, the fast pointer will eventually "lap" the slow pointer and they will meet. If there is no cycle, the fast pointer hits the end first. This simple idea solves an entire family of problems in O(1) space.
Reach for the fast & slow pointers pattern whenever you see these signals:
The alternative is worse: Without this pattern, cycle detection requires a HashSet (O(n) space) to remember visited nodes. Fast & slow pointers achieve the same result in O(1) space.
Consider a linked list where the last node points back to an earlier node, creating a cycle. We deploy two pointers: slow moves 1 step, fast moves 2 steps.
Once both pointers are inside the cycle, think of the gap between them. Each iteration, fast gains exactly 1 step on slow (2 - 1 = 1). So the gap shrinks by 1 every step. No matter how large the cycle, the gap eventually reaches 0 -- they meet.
List: 1 → 2 → 3 → 4 → 5 → 6 → back to 3 (cycle)
// Cycle Detection ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps if (slow == fast) return true; // cycle found! } return false; // fast hit null, no cycle
After detecting the cycle (slow and fast meet), we can find where the cycle begins with a beautiful trick: reset one pointer to the head, then move both at speed 1. They will meet at the cycle start.
Let's define the distances:
This means: starting from the meeting point and walking F more steps lands exactly at the cycle start. And walking F steps from the head also lands at the cycle start. So they meet there!
// Find Cycle Start (Phase 1 + Phase 2) ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Phase 2: reset slow to head, both move at speed 1 slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; // speed 1 now! } return slow; // cycle start } } return null; // no cycle
Since fast moves at 2x speed, when fast reaches the end of the list, slow is exactly at the middle. No need to count the length first!
List: 1 → 2 → 3 → 4 → 5 — watch both pointers advance.
Even-length lists: For a list with even number of nodes (e.g., 1→2→3→4), slow lands on the second middle node (node 3). If you need the first middle, check fast.next != null && fast.next.next != null instead.
// Find Middle of Linked List ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // middle node
Here are all three templates together, fully annotated. These are the building blocks for every fast & slow pointer problem.
public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // tortoise: 1 step fast = fast.next.next; // hare: 2 steps if (slow == fast) return true; // they met = cycle exists } return false; // fast reached end = no cycle }
public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Phase 1: detect cycle slow = head; // Phase 2: reset to head while (slow != fast) { slow = slow.next; // both move at speed 1 fast = fast.next; } return slow; // meeting point = cycle start } } return null; // no cycle }
public ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps } return slow; // when fast stops, slow = middle }
Notice the pattern: All three share the exact same loop structure. The only differences are (1) what happens when slow == fast, and (2) what we return. Master the loop skeleton once, then adapt the response.
These LeetCode problems are solved cleanly using the fast & slow pointers pattern.
#287 Find the Duplicate Number is a particularly clever application: treat the array indices as linked list nodes where nums[i] is the "next" pointer. A duplicate value means two nodes point to the same next -- creating a cycle. Apply Floyd's algorithm to find the duplicate without extra space!
Watch the pointers move step by step through real linked lists.
Cycle detection: If there is no cycle, fast pointer traverses the list once = O(n). If there is a cycle, once both pointers enter the cycle, they meet within at most C steps (where C = cycle length). Since C ≤ n, total work is O(n).
Finding cycle start: Phase 1 is O(n). Phase 2 walks at most F steps (distance from head to cycle start), which is ≤ n. Total: O(n).
Finding middle: Fast pointer traverses the entire list once = O(n). Slow pointer does n/2 steps.
O(1) space is the real win. A HashSet-based cycle detection uses O(n) space to store visited nodes. Floyd's algorithm uses only two pointer variables, no matter how large the input. This is the hallmark of the pattern.
Problems that seem to require O(n) space (storing visited nodes, counting length) can often be solved in O(1) space with fast & slow pointers.
All three use cases share the same while loop. Master it once: while (fast != null && fast.next != null).
Any function f(x) that maps values to values can form a "virtual linked list." Happy Number and Find Duplicate both exploit this.
Finding the cycle start uses two phases: (1) detect with 2x speed, (2) reset one pointer and walk both at 1x. The math guarantees they meet at the start.
The Beauty of Floyd's Algorithm
Two pointers, constant space, linear time. It turns problems that seem to need memory into problems that need only patience -- letting two runners chase each other until the structure of the problem reveals itself.