Pattern 15 · Linked Lists
Fast & Slow Pointers
Floyd's tortoise and hare: two pointers walk the same list at different speeds — one hop vs. two. If there's a cycle, the fast one must lap the slow one; if there isn't, fast hits the end when slow is at the middle. Cycle detection, midpoints, and duplicates in O(1) space.
time O(n)space O(1)phases detect · locatepractice 10 problems
01 core concept
The hare must catch the tortoise
Slow (the tortoise) moves 1 node per round; fast (the hare) moves 2. Once both pointers are inside a cycle, fast gains exactly one node on slow per round — so the gap between them shrinks to zero and they must meet, within one lap. If there is no cycle, fast simply runs off the end. No hash set, no marking nodes: two variables, one pass.
The list used in the walkthrough below — node 8 links back to node 3:
1 → 2 → 3 → 4 → 5
↑ ↓
8 ← 7 ← 6
cycle entry = node 3 · cycle length = 6 (nodes 3–8)
step 1 / 10walkthrough — detect the cycle, then find its entry
slow 1
fast 1
phase 1 · detect
Both pointers start at the head. Remember the hidden edge: 8 links back to 3. Each round: slow takes 1 hop, fast takes 2.
02 the math
Why phase 2 lands on the entry
Name three distances: D from the head to the cycle entry,
C the cycle length, and K from the entry to the
meeting point.
D C (cycle length)
┌────────────────┐ ┌──────────────┐
HEAD ──→ ● ──→ ● ──→ ● ──→ ● ──→ ● ──┐
↑ ENTRY │
│ ↓
● ←── ● ←── ● ←──┘
MEET
When they meet:
Slow traveled: D + K
Fast traveled: D + K + nC (n complete laps)
Fast = 2 × Slow: D + K + nC = 2(D + K)
Therefore: nC = D + K → D = nC − K → D = (n−1)C + (C − K)
Read the last line out loud: the distance from the head to the entry equals the distance from the meeting point to the entry, plus some whole number of laps. So put one pointer at the head and one at the meeting point, march both at speed 1, and they collide exactly at the cycle entry. That's the two-phase algorithm of LC 142 — and, remarkably, of LC 287.
03 recognition
When to reach for it
| signal in the problem | technique |
|---|---|
| "Does this linked list have a cycle?" | Fast/slow — check if they meet |
| "Where does the cycle start?" | Phase 2 — reset one pointer to head |
| "Find the middle of the list" | When fast hits the end, slow = middle |
| "Is this a happy number?" | Cycle detection on a number sequence |
| "Find the duplicate in [1..n]" | Treat the array as an implicit linked list |
| "Is the list a palindrome?" | Find middle + reverse + compare |
| "Reorder the list" | Find middle + reverse + merge |
The deeper signal: you're walking a structure where each element has exactly
one successor — node.next, nums[i],
get_next(n) — and you care about cycles or midpoints while being held
to O(1) extra space.
When NOT to use it
If extra space is allowed, a plain visited hash set detects cycles with
less ceremony — fast/slow earns its keep when O(1) space is required.
And the trick needs a single-successor structure: in a general graph where
nodes have multiple outgoing edges, use DFS with a recursion stack
(or coloring) instead.
04 templates
The three templates to memorize
T1Cycle detection — LC 141
has_cycle.py — LC 141python
def has_cycle(head):
"""Returns True if the linked list has a cycle."""
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow == fast:
return True
return False # fast reached the end -> no cycle
# Why check "fast and fast.next"?
# - fast could be None (even-length list: fast stepped past the end)
# - fast.next could be None (odd-length list: fast is on the last node)T2Find the cycle start (two-phase) — LC 142
find_cycle_start.py — LC 142python
def find_cycle_start(head):
"""Returns the node where the cycle begins, or None."""
# Phase 1: detect the cycle (find the meeting point)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # no cycle
# Phase 2: find the entry point
# Reset one pointer to head; BOTH move at speed 1
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # the cycle entryT3Middle of the list — LC 876
middle_node.py — LC 876python
def middleNode(head):
"""Return the middle node. For even length, the 2nd middle."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# To get the FIRST middle of an even-length list, stop earlier:
def middleNode_first(head):
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow # for [1,2,3,4,5,6]: node 3, not node 4step 1 / 6walkthrough — middle of an even-length list
slow 1
fast 1
Same engine, no cycle: run
while fast and fast.next on 1→…→6. When fast exhausts the list, slow is halfway.Which middle do you want?
while fast and fast.next → 2nd middle (node 4 in [1,2,3,4,5,6]).
while fast.next and fast.next.next → 1st middle (node 3).
For odd-length lists both stop on the exact middle. Choose per problem —
and say which one you chose in the interview.
05 applications
The same trick in four disguises
A1Happy Number — LC 202
No linked list in sight — but get_next gives every number exactly one
successor, so the sequence is an implicit list. Unhappy numbers fall into a
cycle; fast/slow detects it without a hash set.
happy_number.py — LC 202python
def isHappy(n):
"""Happy if the sum-of-squared-digits sequence reaches 1."""
def get_next(num):
total = 0
while num > 0:
num, digit = divmod(num, 10)
total += digit * digit
return total
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow) # 1 step
fast = get_next(get_next(fast)) # 2 steps
return fast == 1
# n = 19: 19 -> 82 -> 68 -> 100 -> 1 HAPPY
# n = 2: 2 -> 4 -> 16 -> 37 -> 58 -> 89
# -> 145 -> 42 -> 20 -> 4 -> ... cycle -> not happyA2Find the Duplicate Number — LC 287
An array of n + 1 integers in range [1, n] has exactly one repeated
value. Treat index → nums[index] as a next-pointer: the duplicate value
is pointed at by two indices, which creates a cycle whose entry is the
duplicate. Full two-phase Floyd, zero extra space.
find_duplicate.py — LC 287python
def findDuplicate(nums):
"""
Array of n+1 integers in range [1, n]. Exactly one duplicate.
Treat the array as a linked list: index -> value = next pointer.
The duplicate creates a cycle; cycle entry = duplicate value.
"""
# Phase 1: find the meeting point
slow = fast = 0 # start at index 0 (the "head")
while True:
slow = nums[slow] # one hop
fast = nums[nums[fast]] # two hops
if slow == fast:
break
# Phase 2: find the cycle entry
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow # the duplicate numbernums = [1, 3, 4, 2, 2] following index → value hops:
index: 0 1 2 3 4 0 → 1 → 3 → 2 → 4 → 2 → 4 → … cycle {2, 4}, entry 2
Phase 1 (slow 1 hop, fast 2): Phase 2 (both 1 hop):
round | slow | fast round | slow | fast
1 | 1 | 3 1 | 1 | 2
2 | 3 | 4 2 | 3 | 4
3 | 2 | 4 3 | 2 | 2 ← entry = duplicate = 2
4 | 4 | 4 ← meet
A3Palindrome Linked List — LC 234
palindrome_list.py — LC 234python
def isPalindrome(head):
"""Check if a linked list is a palindrome. O(n) time, O(1) space."""
if not head or not head.next:
return True
# Step 1: find the middle (first middle for even length)
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 2: reverse the second half
prev = None
curr = slow.next
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# prev is now the head of the reversed second half
# Step 3: compare front half with reversed back half
left, right = head, prev
while right: # the right half is shorter or equal
if left.val != right.val:
return False
left = left.next
right = right.next
return True
# 1 -> 2 -> 3 -> 2 -> 1
# middle = 3; reverse after it: second half becomes 1 -> 2
# compare 1,2 with 1,2 -> palindromeA4Reorder List — LC 143
reorder_list.py — LC 143python
def reorderList(head):
"""Reorder L0 -> L1 -> ... -> Ln to L0 -> Ln -> L1 -> Ln-1 -> ..."""
if not head or not head.next:
return
# Step 1: find the middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Step 2: reverse the second half
prev = None
curr = slow.next
slow.next = None # cut the list in two
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Step 3: interleave the two halves
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
# 1 -> 2 -> 3 -> 4 -> 5
# split: 1 -> 2 -> 3 and 4 -> 5
# reverse: 1 -> 2 -> 3 and 5 -> 4
# merge: 1 -> 5 -> 2 -> 4 -> 3| problem | time | space | notes |
|---|---|---|---|
| Linked List Cycle | O(n) | O(1) | Fast catches slow within one lap |
| Linked List Cycle II | O(n) | O(1) | Two phases, each O(n) |
| Middle of Linked List | O(n) | O(1) | Slow traverses half the list |
| Happy Number | O(log n) | O(1) | Digit processing is O(log n) |
| Find Duplicate Number | O(n) | O(1) | No extra space needed |
| Palindrome Linked List | O(n) | O(1) | Find mid + reverse + compare |
| Reorder List | O(n) | O(1) | Find mid + reverse + merge |
Why O(1) space?
The technique only ever holds two pointer variables, regardless of list
size. No hash sets, no arrays, no recursion stack — which is exactly why
interviewers ask for it.
06 common mistakes
Where the hare trips
Mistake 1 — null-pointer crash on fast
Always check both fast and fast.next before advancing.
while fast.next: alone crashes when fast is already None
(even-length list).
the fixpython
while fast and fast.next: # CORRECT
while fast.next: # WRONG - fast could be NoneMistake 2 — wrong middle for even-length lists
There are two valid middles. while fast and fast.next gives the 2nd
(node 4 in [1,2,3,4,5,6]); while fast.next and fast.next.next gives the
1st (node 3). Pick the one the problem needs.
Mistake 3 — phase 2 at the wrong speed
After the meeting point, both pointers move at speed 1 — not 1 and 2.
The D = (n−1)C + (C−K) math only works at equal speed.
Mistake 4 — infinite loop in Find Duplicate
Start at index 0 (the "head"), not index 1. Values live in [1, n],
so no value ever points back to index 0 — it's guaranteed outside the cycle.
Mistake 5 — not cutting the list at the middle
For palindrome and reorder problems, set slow.next = None to actually
split the list into two halves before reversing.
Mistake 6 — mutating without restoring
Some problems expect the original list intact. If you reversed the second
half, reverse it back afterward — interviewers may ask about it.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
10 problems