skip to content

Fast & Slow Pointers

26 roadmaps8 questions

Two pointers advancing at different speeds through a list or an implicit sequence, so their relative motion reveals cycles and midpoints. Interviewers love it because the O(1)-space answers feel like magic until you can explain the math.

part ofCoding interview patternsoverview, primer and where to startread it →
on this pageshow

explore

questions

8

Why can't a singly linked chain be palindrome-checked by converging pointers from both ends?

level: juniorimportance: must knowfreq 66%

answer

  1. what can a node reach from itself
  2. no index arithmetic on links
  3. a mirror comparison needs both directions
  4. make the back half walkable inward
  5. split, reverse, compare in lockstep

basics

~20 s

A singly linked chain has no backward pointers, so nothing can walk from the tail inward. The standard fix splits the chain at the middle, reverses the back half in place, then compares the two halves node by node.

solid answer

~50 s

Converging-pointer symmetry checks need either random access or a backward link, and a singly linked chain offers neither: from a node you can only move forward, and there is no index arithmetic to jump to position `n-1-i`. So the constant-space answer restructures the problem into three phases — locate the split point at the middle, reverse the back half in place so it becomes walkable from what used to be the tail, then advance one pointer from the head and one from the reversed back half, comparing values as they go. That is O(n) time and O(1) extra space. On an odd length the middle element is its own mirror and never needs a partner, so the comparison is driven by the shorter back half and simply stops when it runs out. The honest caveat: you have mutated a structure the caller still owns.

go deeper

for a junior

Be ready to say out loud why forward-only links block the two-ends trick, and to name the three phases: split at the middle, reverse the back half, compare in lockstep.

for a middle

Explain why the comparison loop is driven by the reversed back half so an odd middle node is skipped for free, and state the O(n) time and O(1) extra space bounds precisely.

for a senior

Point out unprompted that the in-place version mutates a structure the caller still owns, and that the recursive variant's stack makes it linear space rather than constant.

for a principal

Own the choice between the constant-space in-place version and the simpler non-mutating copy, judging by chain length, whether the structure is shared, and who maintains the code.

## The obstacle A symmetry check compares position `i` against position `n-1-i`. On a randomly accessible sequence that is trivial: two indices, one moving up, one moving down, meeting in the middle, O(n) time and O(1) extra space. A singly linked chain gives you neither ingredient. Each node stores a value and exactly one link to its successor. There is no link to a predecessor, and there is no arithmetic that turns "position `n-1-i`" into a node — the only way to reach a position is to walk to it from the head, which makes the naive two-ended version O(n) per comparison and O(n^2) overall. So you have three families of answers, and an interviewer wants you to know all three and to say which one you are choosing. ## 1. Copy the values out (O(n) space) Walk the chain once, appending each value to a growable array (or pushing each onto a stack). Now you have random access, so run the converging-index comparison, or compare the array against the stack popped in reverse. O(n) time, O(n) extra space, and — the property that matters in real code — it does not touch the chain at all. ## 2. Recurse to the tail (O(n) space, hidden) Recurse forward to the end; as each call returns, compare the node it owns against a shared front pointer that you advance one step per return. This genuinely compares back-to-front without any explicit container, and candidates often present it as "constant space". It is not. Recursion depth **is** space: one stack frame per node means O(n) auxiliary space, plus the risk of exhausting the stack on a long chain. The container was not removed, only relocated into the call stack. ## 3. Split, reverse the back half, compare (O(1) space) This is the answer the question is usually testing. 1. **Split.** Find the node where the front half ends, and treat everything after it as the back half. 2. **Reverse the back half in place.** Rewire its links so the old last node becomes the head of that segment. Now the back half is walkable in the direction that a mirror comparison needs, without a single backward pointer having been invented. 3. **Compare.** Run one pointer from the head of the chain and one from the head of the reversed back half, comparing values in lockstep. Time is O(n): a pass to split, a pass to reverse half, a pass to compare half. Extra space is O(1): reversal only rewires existing links, and the routine holds a fixed number of pointers. ## Why the comparison is driven by the back half The two halves are not the same length when `n` is odd. Whichever convention the split uses, one half is one node longer, and that extra node is the middle element — which is its own mirror image and never has to match anything. Driving the loop from the reversed back half (stop when it is exhausted) makes that fall out for free: you compare exactly floor(n/2) pairs and never touch the middle. Driving it from the front pointer instead is the classic off-by-one — you either compare the middle against something it should not be compared against, or walk the front pointer past the split. Even length has no middle node, and the same loop condition still stops after exactly n/2 pairs. One loop, both parities, no special case. ## The price of phase 2 Reversal is destructive. Between the moment you rewire the back half and the moment you rewire it back, the caller's chain is not the chain they handed you: the second half runs the other way, and the front half's tail points at what used to be the last node. If the routine returns without undoing that, the caller receives a mangled structure from what looked like a read-only question. If anything else can observe the chain during the check — an iterator held elsewhere, a callback fired from the comparison — it sees the corruption even if you restore perfectly afterwards. That is the real trade, and it is why option 1 is not a beginner's answer to be embarrassed about: O(n) space buys a check that mutates nothing, has no cleanup path to forget, and can be reviewed at a glance. The constant-space version buys memory at the cost of a window in which a shared structure is briefly invalid. ## What to say out loud "Forward-only links rule out the two-ended trick. With linear extra space I copy the values out and compare converging indices. To get constant space I split at the middle, reverse the back half in place, compare in lockstep driven by the back half so an odd middle is skipped, and then reverse the back half again to hand the caller back what they gave me."

  • Does an odd-length chain need its middle node compared against anything?
    No. The middle element is its own mirror image, so it never needs a partner. That is why the comparison loop is driven by the shorter reversed back half: it stops after exactly floor(n/2) pairs and the middle simply falls outside. Driving the loop from the front pointer instead is the usual off-by-one, and it either compares the middle against the wrong node or walks the front pointer past the split point.
  • What is the alternative when O(n) extra space is allowed?
    Walk the chain once and copy the values into a growable array, or push them onto a stack. Then compare the array with converging indices, or compare a second forward walk against values popped off the stack. It is O(n) time and O(n) space, it mutates nothing, and it is dramatically easier to read and to review than the in-place version.
  • Why is a recursive back-to-front comparison not constant space?
    Because recursion depth is space. Recursing to the tail and comparing on the way out does compare backwards without an explicit container, but it holds one call frame per node, so auxiliary space is O(n) — hidden in the call stack rather than in an array. On a long chain it also risks exhausting the stack, which the explicit-array version simply cannot do.

Proof-reading a scroll that only unrolls one way: you cannot read the end backwards, so you cut it in half and physically flip the second piece over before laying the two side by side.

saying these in an interview costs you the question

  • Claims two pointers can converge from both ends
  • Says a node can be reached backward from the tail
  • Calls the recursive version constant space
  • Compares the middle node against a partner
  • Assumes the in-place check leaves the chain untouched

context

resolving links…

open as a page

What must the step function f guarantee for tortoise-and-hare detection on x = f(x) to be correct?

level: middleimportance: must knowfreq 62%

basics

~20 s

The step must be deterministic and side-effect-free, must give every reachable state exactly one successor over a finite set, and must be cheap to re-evaluate. Branching states, or a walk that can simply end, invalidate the two-pointer loop.

open as a page

When is a visited-set loop check the right call over constant-space fast/slow pointers?

level: seniorimportance: must knowfreq 58%

basics

~20 s

Use a visited set when the state count is small, when the step is expensive enough to want each transition computed once, or when the report must name the looping states. Use two pointers when memory is the binding constraint.

open as a page

Why does iterating x = f(x) over a finite value range always repeat a value?

level: juniorimportance: should knowfreq 52%

basics

~20 s

With finitely many values, among the first N+1 terms two must be equal — pigeonhole. Because the step depends only on the current value, that repeat locks the sequence into a loop forever: tail, then cycle.

open as a page

Why does following i to a[i] in an array whose values are all valid indices guarantee a loop?

level: middleimportance: should knowfreq 45%

basics

~20 s

Every slot holds exactly one valid index, so each position has exactly one successor over finitely many positions. That deterministic walk can never end and can never avoid revisiting a position, so it must fall into a loop.

open as a page

In the split-reverse-interleave reorder of a linked chain, which half gets the odd extra node?

level: middleimportance: should knowfreq 52%

basics

~20 s

The front half keeps the extra node: ceil(n/2) in front, floor(n/2) behind. The splice attaches one back node after each front node, so a longer back half leaves a trailing node with no front node to follow.

open as a page

After the split-and-reverse symmetry check answers, what state is the caller's linked chain in?

level: middleimportance: should knowfreq 45%

basics

~20 s

Unless the back half is reversed a second time before returning, the caller is handed a mangled chain whose second half still runs backward. Restore it on every exit path, including the early return on the first mismatch.

open as a page

When is copying a linked chain into an array the better symmetry check than the O(1)-space one?

level: principalimportance: should knowfreq 38%

basics

~20 s

Copy when the chain is shared or the routine must survive many maintainers: O(n) space buys a check that mutates nothing and has no restore path to forget. Choose the in-place version when memory is the binding constraint.

open as a page