Fast & Slow Pointers
How do you find the middle, or detect a loop, without knowing the length? Send two pointers at different speeds.
The problem
A background job hands you the head of a linked list and asks for the middle node — maybe to split it for a merge sort. Easy enough: count the length, then walk halfway. But that is two passes, and you only realise the length after the first one. Worse, some of these lists have a bug where a node points back into the chain, forming a loop. Your length count never finishes; it just spins.
You want a single pass, no stored length, that finds the middle and can tell whether the list even has an end. Counting first cannot do that — you need something that reacts to the list's shape as it goes.
A first attempt
The two-pass middle finder:
n = 0
node = head
while node: # pass 1: measure
n += 1
node = node.next
node = head
for _ in range(n // 2): # pass 2: walk halfway
node = node.nextIt is O(n) but touches every node twice, needs the length up front, and — fatally — the first loop never terminates on a list with a cycle. For loop detection you might reach for a hash set of visited nodes: correct, but O(n) extra space. There is a way that needs neither the length nor the set.
The insight
Send two pointers from the head at different speeds: slow moves one step, fast moves two.
By the time fast reaches the end, slow has covered exactly half the distance — it is
sitting on the middle. One pass, no counting.
And if the list loops? fast can never reach an end, so it keeps circling and eventually
laps slow from behind. The two pointers meet inside the cycle. Meeting means a loop;
fast hitting null means no loop. This is Floyd's tortoise-and-hare.
slow → one step fast → two steps
[a][b][c][d][e]
s f
s f (fast fell off → slow is at middle)How it works
Both start at the head
slow = head, fast = head. Each iteration, slow advances one node and fast advances
two. The speed gap is the entire mechanism.
Fast reaching null means a clean list
Loop while fast and fast.next are non-null. When it exits, there was no cycle, and slow
is at the middle (the second of the two middles on an even-length list).
Fast meeting slow means a cycle
If a cycle exists, fast re-enters it and closes the gap by one node per step until
fast == slow. That equality is your loop detector — no visited-set required.
Find the loop's start
After they meet, reset one pointer to the head and advance both one step at a time. The node where they meet again is the cycle's entry point — a tidy consequence of the distances involved in Floyd's algorithm.
The code
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def middle(head): # O(n) time, O(1) space
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def has_cycle(head): # Floyd's detection
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return Falseclass ListNode {
value: number;
next: ListNode | null;
constructor(value: number, next: ListNode | null = null) {
this.value = value;
this.next = next;
}
}
function middle(head: ListNode | null): ListNode | null { // O(n), O(1)
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
}
return slow;
}
function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}class Node {
int value;
Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
Node middle(Node head) { // O(n) time, O(1) space
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
boolean hasCycle(Node head) { // Floyd's detection
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}#include <stddef.h>
#include <stdbool.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *middle(Node *head) { /* O(n) time, O(1) space */
Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool has_cycle(Node *head) { /* Floyd's detection */
Node *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}#include <cstddef>
struct Node {
int value;
Node *next;
Node(int v, Node *n = nullptr) : value(v), next(n) {}
};
Node *middle(Node *head) { // O(n) time, O(1) space
Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool has_cycle(Node *head) { // Floyd's detection
Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}Complexity
| Task | Approach | Time | Space |
|---|---|---|---|
| Find middle | Two-pass count | O(n) | O(1) |
| Find middle | Fast/slow | O(n) | O(1) |
| Detect cycle | Visited hash set | O(n) | O(n) |
| Detect cycle | Fast/slow (Floyd) | O(n) | O(1) |
When to use it
Different speeds reveal structure
Fast/slow is the go-to whenever you need a positional landmark (middle, n-th from end, the
split point for merge sort) or must reason about cycles, all in one pass and O(1) space. Its
close cousin: two pointers n apart to find the n-th node from the end. The one gotcha is the
loop guard — check both fast and fast.next before the double hop, or you dereference null
on even-length lists.
Practice
Recap
- Two pointers at 1x and 2x speed find the middle in a single pass with no stored length.
- If
fastlapsslow, the list has a cycle; iffasthits null, it does not — O(1) space. - The same family solves n-th-from-end and the split point for a linked-list merge sort.
How is this guide?
Last updated on