Fast and Slow Pointers Pattern
The Idea
Run two pointers over the same sequence at different speeds — usually 1 step and 2 steps. Their changing distance reveals structure you'd otherwise need extra memory to find.
slow: one step per move 🐢 fast: two steps per move 🐇 NO CYCLE: fast falls off the end → there is no loop CYCLE: fast laps slow inside the loop → they meet MIDDLE: when fast reaches the end, slow has gone half as far
This is also called Floyd's cycle detection or the tortoise and hare technique. It needs O(1) extra space — no visited set.
Use 1: Find the Middle
1 → 2 → 3 → 4 → 5 → 6 → 7 step slow fast 0 1 1 1 2 3 2 3 5 3 4 7 ← fast.next is null → stop. Middle = 4 Even length 1 → 2 → 3 → 4 → 5 → 6: 0 1 1 1 2 3 2 3 5 3 4 null ← stop. slow = 4 (the SECOND middle)
Finding the middle in one pass is the first step of linked-list merge sort, palindrome checks on lists, and "reorder the list" style problems.
Use 2: Detect a Cycle
1 → 2 → 3 → 4 → 5 → 6
↑ │
└───────────────┘ (6 links back to 3)
step slow fast
0 1 1
1 2 3
2 3 5
3 4 3 (5 → 6 → 3)
4 5 5 ← meet! a cycle exists
Use 3: Find Where the Cycle Starts
Let: a = steps from head to cycle start
c = cycle length
when they meet, slow has walked a + b (b steps into the loop)
fast has walked 2(a + b)
fast has gone exactly some whole number of extra laps:
2(a + b) − (a + b) = k · c → a + b = k · c → a = k·c − b
So from the meeting point, walking a more steps lands on the cycle start
(you complete the lap). Walking a steps from the head ALSO lands there.
PHASE 2:
put one pointer at head, keep the other at the meeting point,
move both 1 step at a time → they meet AT the cycle start.
Cycle LENGTH: from the meeting point, walk until you return — count steps.
Use 4: Hidden Linked Lists
Any process where each state has exactly one next state is a linked list in disguise.
DIGIT-SQUARE SEQUENCE next(n) = sum of the squares of n's digits 19 → 1²+9² = 82 → 68 → 100 → 1 → 1 → ... reaches 1 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 ... loops forever Fast/slow tells which, without remembering every number. ARRAY AS A LIST n+1 values, each between 1 and n → at least one value repeats. Treat index i → a[i] as a "next" pointer. Two indices point to the repeated value, so it is the entry point of a cycle. Floyd's phase 2 finds it in O(n) time, O(1) space, without modifying the array.
Code: Middle, Cycle Start, and Hidden Lists
public class FastSlowPointers {
static class Node {
int val; Node next;
Node(int v) { val = v; }
}
// Builds a list; if loopTo >= 0 the tail links back to that index
static Node build(int[] values, int loopTo) {
Node[] nodes = new Node[values.length];
for (int i = 0; i < values.length; i++) nodes[i] = new Node(values[i]);
for (int i = 0; i + 1 < values.length; i++) nodes[i].next = nodes[i + 1];
if (loopTo >= 0) nodes[values.length - 1].next = nodes[loopTo];
return nodes[0];
}
// Middle node — slow moves 1, fast moves 2
static int middle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
return slow.val;
}
// Floyd: returns "starts at X, length L" or "none"
static String findCycle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) { // phase 1: met inside the loop
int length = 1;
for (Node p = slow.next; p != slow; p = p.next) length++;
slow = head; // phase 2: restart one pointer
while (slow != fast) { slow = slow.next; fast = fast.next; }
return "starts at " + slow.val + ", length " + length;
}
}
return "none";
}
// Number sequence: replace n by the sum of squares of its digits
static int digitSquareSum(int n) {
int total = 0;
while (n > 0) { int d = n % 10; total += d * d; n /= 10; }
return total;
}
static boolean reachesOne(int n) {
int slow = n, fast = digitSquareSum(n);
while (fast != 1 && slow != fast) {
slow = digitSquareSum(slow);
fast = digitSquareSum(digitSquareSum(fast));
}
return fast == 1;
}
// n+1 values in 1..n → i -> a[i] is a linked list; the repeat is the loop start
static int repeatedValue(int[] a) {
int slow = 0, fast = 0;
do { slow = a[slow]; fast = a[a[fast]]; } while (slow != fast);
slow = 0;
while (slow != fast) { slow = a[slow]; fast = a[fast]; }
return slow;
}
public static void main(String[] args) {
System.out.println("middle of 1..7: " + middle(build(new int[]{1, 2, 3, 4, 5, 6, 7}, -1)));
System.out.println("middle of 1..6: " + middle(build(new int[]{1, 2, 3, 4, 5, 6}, -1)));
System.out.println("cycle in 1..6 (no loop): " + findCycle(build(new int[]{1, 2, 3, 4, 5, 6}, -1)));
System.out.println("cycle in 1..6 (6 -> 3): " + findCycle(build(new int[]{1, 2, 3, 4, 5, 6}, 2)));
for (int n : new int[]{7, 19, 4, 20})
System.out.println(n + " reaches 1: " + reachesOne(n));
System.out.println("repeated value in [2, 5, 1, 4, 3, 5]: " + repeatedValue(new int[]{2, 5, 1, 4, 3, 5}));
System.out.println("repeated value in [4, 1, 3, 2, 4, 4]: " + repeatedValue(new int[]{4, 1, 3, 2, 4, 4}));
}
}Output:
middle of 1..7: 4
middle of 1..6: 4
cycle in 1..6 (no loop): none
cycle in 1..6 (6 -> 3): starts at 3, length 4
7 reaches 1: true
19 reaches 1: true
4 reaches 1: false
20 reaches 1: false
repeated value in [2, 5, 1, 4, 3, 5]: 5
repeated value in [4, 1, 3, 2, 4, 4]: 4
Fast/Slow vs a Hash Set
| Hash set of visited | Fast/slow pointers | |
|---|---|---|
| Detect a cycle | O(n) time, O(n) space | O(n) time, O(1) space |
| Find cycle start | first repeated node | phase 2 walk |
| Find middle | needs length first (2 passes) | one pass |
| Modifies input? | no | no |
| Easier to explain | yes | needs the meeting-point argument |
When memory is limited, or the interviewer asks for O(1) space, fast/slow is the answer.
How to Spot It
✓ Linked list + "cycle", "loop", "middle", "k-th from the end" ✓ "Without extra space" / "O(1) memory" on a list or sequence ✓ A sequence where each value determines the next one, and you need to know if it repeats ✓ An array of n+1 values in range 1..n, "find the repeat, don't modify the array, O(1) space"
A close relative: "k-th node from the end" — move one pointer k steps ahead, then move both at the same speed; when the leader hits the end, the follower is at the answer. Same idea, equal speeds, fixed gap.
Common Mistakes
Wrong loop condition. while fast.next crashes when fast itself is null. Check fast and fast.next before taking two steps.
Comparing values instead of nodes. Two different nodes may hold the same value. Compare references (is in Python, == on references in Java/C++/JS).
Starting fast one step ahead and then using phase 2 unchanged. The phase-2 argument assumes both start at the head. If you start fast at head.next, the meeting point shifts and the start-finding walk must be adjusted.
Forgetting the self-loop case for number sequences. 1 maps to 1, so the sequence that reaches 1 is a cycle of length 1; check fast == 1 to tell it apart from an unhappy loop.
Interview Questions
Q: Why can fast never jump over slow inside the cycle?
Measure the gap from slow forward to fast. Each step, slow moves 1 and fast moves 2, so the gap shrinks by exactly 1. A quantity that decreases by 1 each step must hit 0 — it cannot skip it — so they land on the same node.
Q: Explain why resetting one pointer to the head finds the cycle start.
At the first meeting, slow has walked a + b steps (a to reach the cycle, b inside it) and fast has walked twice that. The difference, a + b, is a whole number of cycle lengths. So walking a further steps from the meeting point completes laps and lands on the cycle start — and walking a steps from the head also lands there. Moving both at speed 1, they meet exactly at the start.
Q: How would you find the length of the non-cycle part (the "tail")?
Find the cycle start with phase 2, counting the steps taken by the pointer that began at the head. That count is a, the tail length.
Summary
- ›Two pointers at speeds 1 and 2 reveal middles and cycles in O(1) extra space.
- ›Middle: when fast ends, slow is halfway.
- ›Cycle: they meet ⇔ a cycle exists; fast closes the gap by 1 each step.
- ›Cycle start: reset one pointer to the head, move both by 1 — they meet at the start.
- ›Works on any one-successor process: number sequences, index-to-value arrays.
Next, Prefix Sum precomputes running totals so that the sum of any range is a single subtraction — and pairs with a hash map to count subarrays with a target sum, even with negative numbers.
Slow moves 1 step and fast moves 2 steps. If there is no cycle, what happens?