Fast and Slow Pointers
Two runners on one track
Two runners start together, one twice as fast as the other. On a straight road, when the fast one reaches the finish, the slow one is exactly halfway. On a loop, the fast one comes round and catches the slow one from behind.
Two pointers on one list, moving at different speeds or one with a head start, answer the questions a list makes hard: where's the middle, does the list loop, where does the loop start, which node is nth from the end, where do two lists join. Each in one pass, with O(1) extra space.
The first way to find the middle that most people think of is to count, then walk half way:
def middle_by_count(head):
n, curr = 0, head
while curr is not None: # pass 1: count the nodes
n += 1
curr = curr.next
curr = head
for _ in range(n // 2): # pass 2: walk half way
curr = curr.next
return curr
It's correct, and it isn't slow: on a 300,000-node list both it and the two-pointer version below returned node 150,001, in 31.8 ms and 23.8 ms on our judge. Both make about 1.5 n pointer moves: counting walks n nodes and then n / 2, and the two pointers walk n and n / 2 together. The difference is what happens when the list loops. Counting never ends: on 1 → … → 8 with 8 pointing back to 3, the count had reached 1,000,000 when we stopped it.
To detect a loop, the usual first answer remembers every node it has passed:
def has_cycle_with_set(head):
seen = set()
while head is not None:
if head in seen: # a node we've already passed
return True
seen.add(head)
head = head.next
return False
That works, but the set grows with the list. On a 300,000-node list that loops, it took 49.8 ms and 12.6 MB; the two-pointer check took 24.8 ms and no extra memory at all. The rest of this lesson is why two pointers are enough.
The middle in one pass
Start both pointers at the head. Each step, slow moves one node and fast moves two. When fast can't move any further, it has walked twice as far as slow, so slow is halfway:
The middle of 1 to 6 — Slow is indigo and fast amber. When fast steps off the end, slow is on the middle.
Node* middleNode(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != nullptr && fast->next != nullptr) { // fast can take two more steps
slow = slow->next; // one step
fast = fast->next->next; // two steps
}
return slow; // the second middle when the length is even
}
def middle_node(head):
slow = fast = head
while fast is not None and fast.next is not None: # fast can take two more steps
slow = slow.next # one step
fast = fast.next.next # two steps
return slow # the second middle when the length is even
static Node middleNode(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) { // fast can take two more steps
slow = slow.next; // one step
fast = fast.next.next; // two steps
}
return slow; // the second middle when the length is even
}
function middleNode(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) { // fast can take two more steps
slow = slow.next; // one step
fast = fast.next.next; // two steps
}
return slow; // the second middle when the length is even
}
Each printed 3, 4, 1: the middle of 1 to 5, the second middle of 1 to 6, and the only node of a one-node list.
Which middle. An even list has two. while fast and fast.next gives the second. Some problems want the first (Sort List splits a list there), so stop one step sooner:
def first_middle(head):
slow = fast = head
while fast.next is not None and fast.next.next is not None: # stop one step sooner
slow = slow.next
fast = fast.next.next
return slow
On 1 to 6 the two loops gave 4 and 3; on 1 to 5 both gave 3; on 1 to 2 they gave 2 and 1. One pass, O(1) space either way.
A loop: why fast must catch slow
Linked List Cycle asks whether a list loops. Run the same two pointers and check, after every step, whether they're on the same node. This is Floyd's cycle detection, also called the tortoise and the hare. If the list ends, fast reaches null and the answer is no loop. If it loops, fast never reaches null, and the question is whether it could go round forever without ever landing on slow's node.
It can't. Fast enters the loop first. Once slow is in the loop too, count the gap: how many nodes fast has to go round to reach slow. Each step slow moves one node away and fast moves two closer, so the gap shrinks by exactly one: 4, 3, 2, 1, 0. A gap of 1 can only become 0, never jump past it, so they meet. With a nodes before the loop and c nodes in it, that's at most a + c steps: a for slow to reach the loop, then fewer than c to close a gap that's smaller than the loop.
Fast catches slow — The loop is drawn as a ring: 3 to 5 along the top, 6 to 8 back along the bottom, and 8 points up to 3. Slow is indigo, fast amber, green where they meet.
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true; // the same node, not just the same value
}
return false; // fast ran off the end: there's no loop
}
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast: # the same node, not just the same value
return True
return False # fast ran off the end: there's no loop
static boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // the same node, not just the same value
}
return false; // fast ran off the end: there's no loop
}
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // the same node, not just the same value
}
return false; // fast ran off the end: there's no loop
}
Each printed true, true, true, false, false: the loop back to 3, two nodes pointing at each other, one node pointing at itself, a list that ends, and an empty list.
We ran it on every list of 1 to 39 nodes, with the loop starting at every node: 780 lists that loop, and in every one the pointers met within a + c steps. Some met at exactly a + c, so the bound is as tight as it can be.
Note slow is fast: the same node. Comparing values instead is a bug as soon as two nodes hold the same value; it's in the bugs below.
Where the loop starts, and how long it is
Linked List Cycle II asks for the node where the loop starts. After they meet, put one pointer back on the head and move both one node at a time. They meet again exactly where the loop starts.
Why: call the nodes before the loop a, the loop's length c, and the meeting point b nodes past the start. When they met, slow had walked a + b steps and fast twice that. Fast's extra a + b steps were whole laps of the loop, so a + b is a multiple of c. Then a is a whole number of laps minus b: walking a nodes from the meeting point goes round to the start. Walking a nodes from the head reaches the start too. So the two meet there, after exactly a steps.
Back to the head — Slow goes back to the head; fast stays where they met. Both move one node at a time.
Node* detectCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // they met inside the loop
slow = head; // one pointer back to the head
while (slow != fast) { // both one node at a time
slow = slow->next;
fast = fast->next;
}
return slow; // the node where the loop starts
}
}
return nullptr;
}
def detect_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast: # they met inside the loop
slow = head # one pointer back to the head
while slow is not fast: # both one node at a time
slow = slow.next
fast = fast.next
return slow # the node where the loop starts
return None
static Node detectCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // they met inside the loop
slow = head; // one pointer back to the head
while (slow != fast) { // both one node at a time
slow = slow.next;
fast = fast.next;
}
return slow; // the node where the loop starts
}
}
return null;
}
function detectCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) { // they met inside the loop
slow = head; // one pointer back to the head
while (slow !== fast) { // both one node at a time
slow = slow.next;
fast = fast.next;
}
return slow; // the node where the loop starts
}
}
return null;
}
Each printed 3, 7, 1, null: the start of the loop in 1 to 8 (back to 3) and in 1 to 10 (back to 7), the head when the loop takes in the whole list, and null for a single node with no loop. In our run over every list up to 39 nodes, the head reset found the right start every time.
How long the loop is. Cycle Length Detection asks for c. From the meeting point, walk round until you're back:
def cycle_length(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast: # inside the loop: walk round it once
length, curr = 1, slow.next
while curr is not slow:
length += 1
curr = curr.next
return length
return 0 # no loop
It returned 6 for the loop 3 to 8, 4 for 7 to 10, 1 for one node pointing at itself, and 0 for a list that ends. Everything here is O(n) time and O(1) space.
Now you race them
Below, you shape the list: how many nodes come before the loop and how many are in it. Step the two pointers yourself. When slow reaches the loop, the gap appears in the middle of the ring: tap the node where you think they'll meet, then watch the gap close one node per step. After they meet, send slow back to the head and predict where the two meet now; the stage counts the steps both still have to go, and it's the same number for both. Then walk round the loop to measure it.
Try a long way in and a short loop: fast goes round several times, and the head reset still lands on the start. Set the loop to 0 and fast runs off the end, with slow on the middle.
A head start: the nth node from the end
Remove Nth Node From End of List gives you n and only the head. Counting the length first takes two passes. One pass: give fast a head start of n nodes, then move both one node at a time. The gap stays n, so when fast is on the last node, slow is just before the node to remove. Start both on a dummy and removing the head is the same write as removing any other node.
Remove the 2nd node from the end — The dashed box is the dummy. Fast (amber) moves ahead alone, then both move together.
Node* removeNthFromEnd(Node* head, int n) {
Node dummy(0, head); // so removing the head is the same write
Node* slow = &dummy;
Node* fast = &dummy;
for (int k = 0; k < n; k++) // fast gets a head start of n nodes
fast = fast->next;
while (fast->next != nullptr) { // both move until fast is on the last node
slow = slow->next;
fast = fast->next;
}
Node* gone = slow->next; // slow is just before the one to remove
slow->next = gone->next;
delete gone;
return dummy.next;
}
def remove_nth_from_end(head, n):
dummy = Node(0, head) # so removing the head is the same write
slow = fast = dummy
for _ in range(n): # fast gets a head start of n nodes
fast = fast.next
while fast.next is not None: # both move until fast is on the last node
slow = slow.next
fast = fast.next
slow.next = slow.next.next # slow is just before the one to remove
return dummy.next
static Node removeNthFromEnd(Node head, int n) {
Node dummy = new Node(0, head); // so removing the head is the same write
Node slow = dummy;
Node fast = dummy;
for (int k = 0; k < n; k++) // fast gets a head start of n nodes
fast = fast.next;
while (fast.next != null) { // both move until fast is on the last node
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; // slow is just before the one to remove
return dummy.next;
}
function removeNthFromEnd(head, n) {
const dummy = new Node(0, head); // so removing the head is the same write
let slow = dummy;
let fast = dummy;
for (let k = 0; k < n; k++) // fast gets a head start of n nodes
fast = fast.next;
while (fast.next !== null) { // both move until fast is on the last node
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; // slow is just before the one to remove
return dummy.next;
}
Each printed 1 -> 2 -> 3 -> 5 -> null for n = 2 on 1 to 5, 2 -> 3 -> 4 -> 5 -> null for n = 5 (the head itself, thanks to the dummy), null for the only node, and 1 -> null for the last of two.
Delete the Middle Node of a Linked List needs the node before the middle, because that's the one whose pointer changes. Start fast two nodes ahead and slow stops one node earlier:
def delete_middle(head):
if head.next is None: # one node: the list becomes empty
return None
slow, fast = head, head.next.next # fast starts two ahead, so slow stops before the middle
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next # unlink the middle
return head
It turned 1 → 3 → 4 → 7 → 1 → 2 → 6 into 1 -> 3 -> 4 -> 1 -> 2 -> 6 -> null, 1 → 2 → 3 → 4 into 1 -> 2 -> 4 -> null, 2 → 1 into 2 -> null, and a single node into null.
Where two lists join
Intersection of Two Linked Lists gives two heads whose lists may merge into one shared tail. The trouble is that the parts before the join can have different lengths, so two pointers walking in step miss each other.
The fix: when a pointer runs off the end of its list, send it to the other list's head. Now p walks A's own nodes, the shared part, then B's own nodes, and q walks B's, the shared part, then A's. Both totals are the same, so they arrive at the first shared node together. If nothing is shared, they reach null together and the loop ends there.
Switch lists at the end — p is indigo and q amber; the shared part is teal. A pointer that runs off its list starts again on the other list's head.
def get_intersection_node(head_a, head_b):
p, q = head_a, head_b
while p is not q: # the same node, or both null
p = p.next if p is not None else head_b # off the end of A: carry on along B
q = q.next if q is not None else head_a # off the end of B: carry on along A
return p # the first shared node, or None
It returned the node holding 7, the shared one (r is shared printed True), after 8 steps each. For 2 → 6 → 4 and 1 → 5, which share nothing, it returned None. O(a + b) time, O(1) space.
Happy Number: a list you never build
Happy Number has no list in it. Replace a number by the sum of the squares of its digits, and repeat: from 19 you get 19 → 82 → 68 → 100 → 1, and 1 leads to 1 forever. From 2 you get 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, and 4 comes round again, so it loops without ever reaching 1.
Each number is a node, and its next node is computed, not stored. Floyd needs nothing else, so it finds the loop without a set of every number seen:
def digit_square_sum(n):
total = 0
while n > 0:
n, d = divmod(n, 10)
total += d * d
return total
def is_happy(n):
slow, fast = n, digit_square_sum(n)
while fast != 1 and slow != fast: # a number is its own node, so equal values are the same node
slow = digit_square_sum(slow)
fast = digit_square_sum(digit_square_sum(fast))
return fast == 1
The happy numbers below 30 came out as 1, 7, 10, 13, 19, 23, 28, and is_happy(19) and is_happy(2) returned True and False. Here comparing values is right, because the value is the node.
Palindrome Linked List uses this lesson's middle and the reversal from Reversing a Linked List: find the middle, reverse the second half, compare the halves, and reverse it back.
Spotting it, and when it breaks
The clues. The middle of a list; whether it loops, where, and how long the loop is; the nth node from the end; the node before the middle; where two lists meet. Also any "next state" you compute rather than store, like Happy Number: a sequence that must either reach a target or repeat. And the usual add-on: one pass, O(1) extra space.
The near-misses. If memory doesn't matter, a set of visited nodes is simpler and finds the loop's start directly. And if you already know the length, a single walk of length − n finds the nth from the end.
When it breaks. Floyd needs a fixed next: each node or number must always lead to the same next one. It compares nodes, not values, unless the value is the node, as in Happy Number. And on a list that might loop, every walk except fast and slow's needs a guard, or it never ends.
Bugs that cost a submission
Reading fast.next.next without checking fast. This middle loop only checks fast.next:
def middle_node(head):
slow = fast = head
while fast.next is not None: # never checks fast itself
slow = slow.next
fast = fast.next.next
return slow
On 1 → 2 it raised AttributeError: after one step fast is null, and the loop reads fast.next from it. Check fast before fast.next.
Comparing values instead of nodes.
def has_cycle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow.val == fast.val: # compares values, not nodes
return True
return False
On 1 → 5 → 5 → 3, which doesn't loop, it returned True: after one step slow is on the first 5 and fast on the second. Comparing the nodes returned False.
The plain middle in Delete the Middle Node. Slow lands on the middle, not before it:
def delete_middle(head):
if head.next is None:
return None
slow = fast = head # the plain middle loop
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
slow.next = slow.next.next # slow is on the middle, so this unlinks the node after it
return head
On 1 → 3 → 4 → 7 → 1 → 2 → 6 it returned 1 -> 3 -> 4 -> 7 -> 2 -> 6 -> null: 7 stayed and the 1 after it went. The answer is 1 -> 3 -> 4 -> 1 -> 2 -> 6 -> null.
A head start of n − 1. Remove Nth with the loop one short removed the wrong node: 1 -> 2 -> 3 -> 4 -> null for n = 2 on 1 to 5, where the answer is 1 -> 2 -> 3 -> 5 -> null.
No dummy before the head.
def remove_nth_from_end(head, n):
slow = fast = head # no dummy before the head
for _ in range(n):
fast = fast.next
while fast.next is not None: # fast is null when the head is the one to go
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head
With n = 5 on 1 to 5 the head has to go, the head start takes fast off the end, and fast.next raised AttributeError. A dummy gives slow a node to stand on before the head.
Check yourself
Quiz
1 / 6Multiple choice
while fast and fast.next. Which node is slow on when it stops?Multiple choice
Multiple choice
Multiple choice
slow.val == fast.val. What does it return on 1 → 5 → 5 → 3, which doesn't loop?Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Middle of the Linked List: slow one, fast two.
- Linked List Cycle: they meet if and only if it loops.
- Happy Number: the same check on a list you never build.
- Intersection of Two Linked Lists: switch lists at the end.
- Palindrome Linked List: the middle, then reverse the second half.
- Remove Nth Node From End of List: a head start of n, from a dummy.
- Delete the Middle Node of a Linked List: stop before the middle.
- Linked List Cycle II: back to the head finds the start.
- Cycle Length Detection: walk round once from the meeting point.
Next, Merging and Splitting Linked Lists: rearranging a list by moving nodes onto a new tail.