Fast / Slow Pointers

What is this?

A linked list is a chain of nodes where each one only points to the next — like a treasure hunt of clues you can only follow forward. Since you can't jump to a position, you send two walkers down the chain at once: one fast and one slow. By watching where the slow walker is when the fast one reaches the end, you learn things like the middle of the list or where two chains join, all in a single pass.

💡 Fun fact: The fast-and-slow trick is also called Floyd's tortoise and hare algorithm, named after Robert W. Floyd; if the two walkers ever land on the same node, the list secretly loops back on itself.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: You can't index a linked list, so you bring the answer to you with a second pointer. Move one pointer faster than the other (or keep a fixed gap behind it), and a single forward pass reveals the midpoint, the nth-from-end, or where two lists join — all in O(1) memory.

Why a second pointer is the whole trick

A forward-only list hides anything that depends on position relative to the end or total length — you'd normally need a first pass to measure. A cleverly-moving second pointer encodes that information while you walk:

• Different speeds (fast = 2× slow): when fast reaches the end, slow is at the middle (and if there's a cycle, they meet).
• Fixed gap (fast starts n ahead): when fast falls off, slow sits exactly where the nth-from-end action happens.
• List-switching (walk A→B and B→A): both pointers traverse lenA + lenB, cancelling the length difference so they align.

The three problems

• Middle of the Linked List — slow ×1, fast ×2; fast at end ⇒ slow at middle (return the second middle on even length). One pass.
• Intersection of Two Linked Lists — pointer a does A-then-B, b does B-then-A; after lenA+lenB steps they meet at the join (or both reach None if disjoint). No length math.
• Remove Nth Node From End — advance fast n nodes, then move both until fast hits the end; slow is just before the target. A dummy head makes removing the head uniform.

The pattern

The insight: relative motion is position. Half-speed ⇒ halfway; a gap of n ⇒ n from the end; equal total distance ⇒ aligned. Pick the motion that encodes what you need, and one pass does it in O(1) space.

📓 Draw it yourself

1. Tortoise & hare. Draw a 6-node list; step slow (×1) and fast (×2) and mark where slow lands when fast exits — the midpoint.
2. The gap. For Remove Nth, draw two pointers n apart and slide them together until the front leaves the list; the back is one before the target.

Snap photos and embed them with the /host-diagrams skill.

Key takeaways

• A second pointer replaces a length pass — different speed, fixed gap, or list-switch.
• Tortoise & hare finds the midpoint (and cycles) in one pass, O(1) space.
• Fixed gap of n finds the nth-from-end; pair it with a dummy head.
• Switch-lists cancels the length gap between two lists — no counting.
• Why interviewers love it: it shows you can extract position/length info from a forward-only structure without extra memory.

Order: Middle of the Linked List → Intersection of Two Linked Lists → Remove Nth Node From End.