cf.completefrontend
LINKED LISTS · CORE

Fast and slow pointers

Walk two pointers through a list at different speeds, so where one is tells you something about where the other is.

Time O(n)Space O(1)10 practice problemsStep-through picture

The idea

Some questions about a linked list depend on its length: find the middle node, or the node three places from the end. With an array you would compute the index. A linked list doesn't know its length, so you would have to walk it twice: once to count, once to reach the spot.

Fast and slow pointers answer these questions in one walk. Two variables start at the head. slow moves one node per step and fast moves two. When fast reaches the end, slow has gone exactly half as far, so it stands on the middle node.

The same idea works with a fixed gap instead of a different speed: move fast k nodes ahead first, then move both one node at a time. When fast falls off the end, slow is k nodes from the end.

An everyday example

Two friends on a running track

Two friends start a straight 10 km run at the same time. One runs twice as fast as the other. When the fast runner crosses the finish line, you don't need a map to know where the slow runner is: exactly at the 5 km mark, the middle of the course.

How the example maps to the code
In the exampleIn the code
The start linehead
The slow runner, one step at a timeslow = slow.next
The fast runner, two steps at a timefast = fast.next.next
The fast runner crosses the finishfast === null || fast.next === null
Where the slow runner standsthe middle node, slow

From the slow way to fast and slow pointers

  1. Start with the obvious way to find the middle node. Walk the whole list once to count its length n, then walk again from the head for n / 2 steps. That works, but it reads the list one and a half times, and it needs two separate loops even though the answer only depends on where the end is.
  2. The useful fact is that two walkers moving at fixed speeds always keep a fixed relationship. If one walker moves twice as fast as the other, then after any number of steps it has gone exactly twice as far. Its position tells you the other's position without any counting.
  3. So start slow and fast at the head. Each loop, slow takes one step and fast takes two. fast reaches the end when it has gone about n nodes, and at that moment slow has gone about n / 2. One walk, no counter, and slow stands on the middle.
  4. The loop needs one guard: fast takes two steps, so both fast and fast.next must exist before it moves. The same idea works with a fixed gap instead of a different speed, for the node k from the end. That loop is fast and slow pointers.

How it works

  1. Start both slow and fast at head.
  2. While fast and fast.next both exist, fast can still take two steps.
  3. Move slow one node forward: slow = slow.next.
  4. Move fast two nodes forward: fast = fast.next.next.
  5. When the loop stops, fast is at the last node or past it, and slow is at the middle. Return slow.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function middleNode(head) {
  2. let slow = head;
  3. let fast = head;
  4. while (fast !== null && fast.next !== null) {
  5. slow = slow.next;
  6. fast = fast.next.next;
  7. }
  8. return slow;
  9. }

How fast it is

TimeO(n)
Extra memoryO(1)

fast reaches the end after about n / 2 loops, and each loop does a fixed amount of work. Only two pointers are stored.

  • Best caseO(n)

    Any list of n nodes. The loop always runs exactly floor(n / 2) times, so no input lets it stop early.

  • Average caseO(n)

    Any list: the work depends only on the length, not on the values stored in the nodes.

  • Worst caseO(n)

    Any list: fast visits about every node once on its way to the end, which is about n / 2 loops of two steps.

Common mistakes

  • Checking only fast.next !== null in the loop. On an empty list fast is null, and reading fast.next throws an error. Check fast !== null first.
  • Mixing up which middle you get for even lengths. Decide whether you need the first or second middle and pick the loop condition to match.
  • In the fixed-gap version, moving fast k - 1 or k + 1 times instead of k. Trace a three-node list by hand to check the gap.
  • Cutting the list in half without setting the first half's last next to null, which leaves the two halves still joined.

When to use it

Look for these clues in a problem:

  • You need the middle node, or the node k places from the end, of a linked list.
  • The task asks for one pass over the list, or O(1) extra space.
  • The task splits a list into two halves, for example to compare, fold, or sort them.
  • The question asks whether a sequence of moves ever loops (see Floyd's cycle detection).

Check yourself

Answer each one in your head first, then open it.

In a list of 7 nodes, how many times does the loop run and where does slow stop?

It runs 3 times, floor(7 / 2). slow stops at index 3, the fourth node, which is the exact middle.

Why check fast !== null before fast.next !== null?

On an empty list, or when fast jumped off the end, fast is null, and reading null.next throws an error. The && stops before that read.

Can slow ever pass fast?

No. After s loops fast is at index 2s and slow at s, and 2s >= s always. They are only equal at the start.

In the fixed-gap version, why does slow end exactly k from the end?

Both move one node per loop after the head start, so the gap between them stays k. When fast is null, one past the last node, slow is k nodes before that point.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: after s loops, slow is the node at index s and fast is the node at index 2s, counting the head as index 0. It holds at the start with s = 0, and each loop adds one to slow's index and two to fast's, so it keeps holding.

The loop continues only while index 2s + 1 exists, that is while 2s + 1 is at most n - 1. So it stops at the first s with 2s + 1 >= n, which is s = floor(n / 2). For n = 6 that is 3, and for n = 5 it is 2, matching the trace.

Index floor(n / 2) is the exact middle when n is odd and the second of the two middles when n is even. The loop always ends, because fast moves forward two nodes every time and a list without a cycle has an end.

Going deeper

4 more ideas

Why slow ends on the middle

After s steps, slow has moved s nodes and fast has moved 2s nodes. The loop stops when fast can't take two more steps, which is when 2s is about the length n. So s is about n / 2: slow is halfway down the list.

Choosing the first or second middle

With an even number of nodes there are two middle nodes. The loop above lands on the second. To land on the first one, for example to cut a list into two halves where the first half is not shorter, loop while fast.next !== null && fast.next.next !== null.

The fixed-gap variation

To find the node k places from the end, move fast forward k times first, then move slow and fast together one node at a time. The gap between them stays k, so when fast is null, slow is k nodes from the end. Starting slow at a dummy node before the head makes slow stop one node earlier, which is handy when you want to remove that node.

Cost

fast walks the list once, so the time is O(n). Only two pointers are kept, so the extra space is O(1). Counting the length first and then walking to the middle is also O(n), but it reads the list one and a half times instead of once.

Work it by hand

Every step in a table, with why

Find the middle of a six-node list. With an even length there are two middles, and this loop lands on the second.

head = 11 -> 24 -> 35 -> 47 -> 52 -> 68

StepLoopslowfastfast.nextWhat happensWhy
1start111124Both exist: loop runsBoth pointers start at the head. fast and fast.next both exist, so fast can take two steps.
21243547Both exist: loop runsslow moved one node and fast moved two. fast is at index 2, twice slow's index 1.
32355268Both exist: loop runsfast is at index 4. Its next, 68, is the last node, so one more double step is allowed.
4347null-fast is null: stopfast jumped from 52 over 68 and off the end. The loop stops and slow is at index 3.

It returns the node 47, the fourth of six, after 3 loops. With five nodes, 11 to 52, the loop would stop after 2 loops because fast.next is null at 52, and slow would be 35, the true middle.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Fast and slow pointersO(n)O(1)You need the middle or the kth from the end in one pass, with no extra memory.
Count first, then walkO(n)O(1)You want the most obvious code and don't mind reading the list one and a half times.
Copy the nodes into an arrayO(n)O(n)You will ask many position questions about the same list, so jumping by index pays for the copy.

Extra memory: O(1): two pointers, slow and fast, whatever the length. Nothing is copied.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Fast and slow pointers and the other approaches, on a scale where each line up is 10 times more steps.
  • Fast and slow pointers, Count first, then walk, Copy the nodes into an array O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Fast and slow pointers101,0001 million
Count first, then walk101,0001 million
Copy the nodes into an array101,0001 million

Inputs that need care

5 tricky inputs
An empty list: head = null
fast !== null is false at once, so the loop never runs and the function returns slow, which is null. This is why the fast check comes first.
One node
fast.next is null, so the loop never runs and the head itself is the middle.
Two nodes, 3 -> 8
One loop runs: slow moves to 8 and fast goes to null. The answer is 8, the second middle. Use the first-middle condition if you need 3.
Fixed gap k larger than the length
Moving fast forward k times reaches null early and the next fast.next throws an error. Check for null while placing fast, and decide what to return when the list is too short.
A list with a cycle
fast never reaches null, so this loop never ends. If the data can loop, use Floyd's cycle detection, which adds a slow === fast check.

Variations and follow-ups

Twists interviewers add

First middle instead of second

Loop while fast.next !== null && fast.next.next !== null. Then on six nodes slow stops at index 2 instead of 3. This is the version you want before cutting a list into two halves where the first half is not shorter.

The kth node from the end

Move fast forward k nodes first, then move both one node at a time until fast is null. The gap stays k the whole time, so slow ends k nodes from the end. Start slow at a dummy node if you want to stop one node earlier and remove it.

Palindrome check in O(1) space

Find the first middle, reverse the second half in place, then walk both halves side by side comparing values. Reverse the second half back afterward if the caller still needs the list.

Split for merge sort

Merge sort on a linked list finds the first middle, sets its next to null to cut the list in two, sorts each half, and merges them. Fast and slow pointers make the split one pass with no counting.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the words "middle", "kth from the end", "in one pass", or "O(1) extra space" on a linked list. Any question whose answer depends on the list's length is a hint.
  • Say the rule out loud: "after s loops, slow is at index s and fast is at 2s, so when fast hits the end, slow is halfway." Then explain the guard: fast takes two steps, so check fast and fast.next.
  • Test by hand on lists of length 0, 1, 2, and 3. They show the empty-list guard and which middle you get for even lengths.
  • Expect the follow-up "which middle do you return for an even length, and how would you get the other one?". Answer with the two loop conditions and trace a four-node list to show both.

Where frontend code uses it

The same idea in real UI code
  • Finding the middle of a linked structure is the first step of merge sort on a linked list, which some editors and libraries use to sort linked records without copying them into an array.
  • The fixed-gap idea is how you would show "the last 20 entries" of a long linked log or undo history in one pass without counting it first.
  • The faster and slower walker idea also detects loops, such as a chain of redirects or a parent chain in a broken tree of UI nodes that points back to itself.

Related algorithms