Fast & Slow Pointers

Two pointers walk the same sequence at different speeds. The gap between them finds cycles, the middle of a list and the k-th node from the end, all in O(1) extra space.

Overview

The idea

A linked list has no length field and no index. To learn something about its shape you have to walk it. The fast and slow pointer technique walks it once with two pointers: slow moves one node per step and fast moves two. What you learn comes from the gap between them.

Is there a cycle? — fast reaches the end (no cycle) or catches slow (cycle)
Where is the middle? — when fast reaches the end, slow has covered half the distance
Where is the k-th node from the end? — start fast k nodes ahead; when fast runs off the end, slow is on the k-th node from the end
Where does the cycle start? — after the pointers meet, walk one pointer from the head and one from the meeting point at the same speed

The cycle test is usually called Floyd's tortoise and hare. Knuth credited it to Robert W. Floyd, but it does not appear in Floyd's published work and may be folklore. The alternative is a set of visited nodes, which costs O(n) extra space. The two pointers cost O(1).

Cycle detection

Once both pointers are inside the cycle, fast gains exactly one node on slow at every step. The gap shrinks by one each time, so fast cannot jump over slow: within one lap they stand on the same node.

The trace below runs on the list 1, 2, 3, 4, 5, 6 where node 6 points back to node 3.

0 — 1 — 1
1 — 2 — 3
2 — 3 — 5 — 2
3 — 4 — 3 — 1
4 — 5 — 5 — 0, they meet

Finding where the cycle starts

After the meeting, put one pointer back at the head and leave the other at the meeting point. Move both one node per step. They meet at the first node of the cycle. In the example: 1 and 5, then 2 and 6, then 3 and 3.

Why this works. Call L the number of nodes from the head to the cycle start, C the cycle length and K the distance from the cycle start to the meeting point. When they meet, slow has walked L + K and fast has walked 2(L + K). The difference, L + K, is a whole number of laps, so L + K = mC for some m. Then L = mC - K: a pointer that starts at the meeting point and walks L steps ends K + L = mC nodes past the cycle start, which is the cycle start itself. In the example L = 2, C = 4, K = 2 and m = 1.

The middle of a list

Both pointers start at the head. When fast runs out of list, slow is at the middle. For an even length there are two middle nodes, and the stop condition decides which one you get.

5 — 1 2 3 4 5 — 3 — 3
6 — 1 2 3 4 5 6 — 4 (second middle) — 3 (first middle)

The trace for 1 to 6 with the first condition: slow 1, 2, 3, 4 while fast goes 1, 3, 5, then null. Say which middle the problem wants before you code. Middle of the Linked List wants the second one; splitting a list in half for merge sort or a palindrome check usually wants the first.

The k-th node from the end

Move fast k nodes ahead first. Then move both one node at a time until fast runs off the end. The gap stays k, so when fast is one past the last node, slow is on the k-th node from the end, counting the last node as the first. On 1, 2, 3, 4, 5 with k = 2: the pairs are (1, 3), (2, 4), (3, 5), then (4, none), and slow stops on 4. Stop one step earlier, while fast is still on the last node, and slow is on the node before the k-th, which is the one you need for Remove Nth Node From End of List.

Cycles that are not linked lists

Any rule of the form next = f(current) on a finite set of values must eventually repeat, so it is a linked list in disguise. The two pointers work unchanged, and they replace a visited set.

Happy Number — integers — sum of the squares of the digits — the number is not happy
Find the Duplicate Number — indexes 0 to n — index to nums[index] — the duplicate is the cycle start

Happy Number: 19 goes 82, 68, 100, 1 and stops. Every unhappy number in base 10 ends in the loop 4, 16, 37, 58, 89, 145, 42, 20 and back to 4. Run the two pointers until fast is 1 (happy) or slow equals fast (not happy).

start — 19 — 19
1 — 82 — 68
2 — 68 — 1, so 19 is happy

Find the Duplicate Number: n + 1 values in the range 1 to n, and one value repeats. Treat each index as a node and nums[i] as its next pointer. Index 0 is never pointed at, so the walk from 0 leads into a cycle, and the node where the cycle starts is the value that two indexes point at. On [1, 3, 4, 2, 2], the two pointers start at nums[0] = 1, meet at 2, and the second walk from the head also ends at 2.

What you will be able to do

Detect a cycle and find its first node, and prove why the second walk lands there.
Return the middle of a list, choosing the right middle for even lengths.
Find the k-th node from the end in one pass.
Spot a hidden cycle in a number sequence or an array and apply the same code.
Explain the O(1) space advantage over a visited set.

When to use it

Deciding whether a linked list has a cycle, and where it starts
Finding the middle of a linked list in one pass, for splitting or palindrome checks
Finding the k-th node from the end without knowing the length
Detecting a repeat in a sequence defined by next = f(current), such as Happy Number
Finding the duplicate in an array of n + 1 values from 1 to n, with O(1) extra space and no changes to the array

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio