Fast & slow pointers

Two pointers walk the same list at different speeds. When the fast one reaches the end, the slow one is halfway; if the list loops, the fast one laps the slow one. Both answers cost O(1) memory.

3 examples11 to practiceRead · 5 min
The idea

A pointer moving twice as fast tells you about the whole list

A linked list doesn't know its length, and the only way through it is from the head. Fast and slow pointers start two references at the head and move them together: slow one node per step, fast two.

Two facts follow:

  • when fast falls off the end, slow has covered half the distance, so it stands at the middle;
  • if the list loops back on itself, fast never falls off. It goes round the loop and, gaining one node per step, eventually lands on the same node as slow.

The rule

Move slow one step and fast two. If fast reaches the end, slow is at the middle; if they ever meet, the list has a cycle. Either way it takes O(n) time and O(1) extra memory.

Spotting it

Linked lists, middles and loops, with no extra memory

The middle of a linked list

slow, when fast reaches the end

Does the list loop back? Where does the loop start?

A meeting, then a second walk

A sequence of values where each one leads to the next, and might repeat

The same cycle check, on values instead of nodes

"In O(1) extra space", where a set of visited nodes would be the easy answer

Two pointers replace the set

Basic

Find the middle node

The plainest case. Each step, slow moves one node and fast two, so when fast has nowhere to go, slow has gone half as far.

With an even number of nodes there are two middles; this loop stops at the second one, which is the usual convention. Checking fast.next.next instead of fast.next stops at the first.

Medium

Find where a loop begins

Now the last node links back into the list. First run the pointers until they meet, which proves there is a loop. Then a short piece of arithmetic finds where the loop starts.

Say the loop starts a nodes from the head, and the pointers meet b nodes into the loop. slow walked a + b nodes; fast walked twice that, 2(a + b), which is the same position plus some whole number of laps. So a + b is a whole number of laps, and walking a more nodes from the meeting point covers a + b from the loop's start, some whole number of laps: it lands exactly at the loop's start. Walking a nodes from the head lands there too. So put slow back at the head, move both pointers one node at a time, and they meet at the start of the loop.

Hard

A list of values can hide a linked list

No nodes here, just numbers. Read each value as "go to that position next". Every value is between 1 and n, so following links never runs off the end and must eventually loop. Nothing links to position 0, so it acts like the head of a list. The loop's entry is a position reached both from outside the loop and from inside it: two positions link to it, so its number is the repeated value. The same two-speed walk finds that entry.

The template

The shape to reuse

  1. 1slow ← head
  2. 2fast ← head
  3. 3while fast ≠ nothing and fast.next ≠ nothing
  4. 4 slow ← slow.next
  5. 5 fast ← fast.next.next
  6. 6 if slow = fast
  7. 7 -- a cycle
  8. 8-- no cycle: slow is the middle
Traps

Where fast-and-slow solutions go wrong

Reading past the end

Check both fast and fast.next before taking fast.next.next; either can be nothing.

Comparing values instead of nodes

Two different nodes can hold the same value. slow = fast must ask whether they are the same node.

Checking before moving

If both start at the head, they are "equal" before moving; move first, then check.

When memory is no concern

A hash set of visited nodes also finds a cycle, in O(n) time and O(n) memory, and is often simpler to get right. The pointers are the answer when O(1) memory is asked for.

Check yourself

3 questions

1. A linked list has 5 nodes. slow moves one node per step and fast two, both from the head. Where is slow when fast can't move again?
2. Why must slow = fast compare nodes and not the values they hold?
3. The pointers have met inside a loop. How do you find the node where the loop starts?
Takeaways

Remember this

  • Move slow one node and fast two: when fast reaches the end, slow is at the middle.
  • If the list loops, fast laps slow and they meet; restarting slow at the head and moving both one step finds the loop's start.
  • It uses O(1) extra memory; a hash set of visited nodes is the simpler O(n)-memory alternative.
Practice

Now solve some yourself

Only this topic 0 of 9 solved

  1. Easy
    Does a list loop back?
    Fast & slow pointers
    LeetCode 141(opens in a new tab)
  2. Easy
    Who gets the second hole in their badge?
    Fast & slow pointers
    Codeforces 1020B(opens in a new tab)
  3. Easy
    Where k teleports land you, with k up to 10^18
    Fast & slow pointers
    AtCoder abc167_d(opens in a new tab)
  4. Easy
    Does repeatedly summing squared digits reach 1?
    Fast & slow pointers
    LeetCode 202(opens in a new tab)
  5. Easy
    Does a list read the same backward?
    Fast & slow pointers
    LeetCode 234(opens in a new tab)
  6. Medium
    Remove the middle node of a list
    Fast & slow pointers
    LeetCode 2095(opens in a new tab)
  7. Medium
    Interleave a list with its own reverse half
    Fast & slow pointers
    LeetCode 143(opens in a new tab)
  8. Medium
    Largest sum of a node and its mirror
    Fast & slow pointers
    LeetCode 2130(opens in a new tab)
  9. Medium
    Does a circular list of jumps loop?
    Fast & slow pointers
    LeetCode 457(opens in a new tab)

Mixed with topics you have practiced 0 unlocked

    2 more once you have practiced Two pointers, Merge sort & quicksort. Play one of its examples to the end and solve one of its problems to unlock them.

    Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.

    Next

    Monotonic stack & queue

    Continue