Fast and slow pointers

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A linked list is a chain of boxes, each holding a value and an arrow to the next box. The chain 3 → 2 → 0 → −4 looks normal, except the last box's arrow points back to the box holding 2. Follow the arrows and you go 3, 2, 0, −4, 2, 0, −4, 2, … forever. Does this chain have a loop? And where does the loop start?

By hand you would keep a list of every box you have visited, and stop the first time you reach a box already on the list. That works, but the list of visited boxes needs as much memory as the chain itself. For a chain of a million boxes, a million notes.

Here is a different idea from running tracks. Put two runners on the chain, one walking one box per step and one running two boxes per step. On a straight chain the fast runner reaches the end and the game is over. On a loop, the fast runner goes round and round and must eventually catch up with the slow one from behind. Two runners, no notes.

Build the structure, one piece at a time

No new container is needed, only two pointers into the existing chain.

Piece 1: two pointers at the head. slow and fast both start at the box holding 3.

Piece 2: unequal speeds. Each step, slow follows one arrow and fast follows two. If fast reaches a box with no next box, the chain is straight: no loop.

Piece 3: the meeting test. After each step, if slow and fast are the same box, there is a loop.

Piece 4: finding where the loop starts. Leave one pointer at the meeting box and move the other back to the head. Now walk both one box per step. They meet exactly at the first box of the loop. Here: head pointer 3 → 2, meeting pointer −4 → 2. Both at 2, so the loop starts at the box holding 2.

Why it is correct

The invariant: after t steps, slow is t arrows from the head and fast is 2t arrows from the head.

Why must they meet inside a loop? Once both are in the loop, look at the gap from slow forward to fast, measured in boxes around the loop. Each step slow moves 1 and fast moves 2, so the gap grows by 1 modulo the loop length L. A gap that grows by 1 each step hits every value, including 0, within L steps. Gap 0 means the same box.

Why does the second phase find the loop start? Let the straight part before the loop have a boxes and let the meeting point be b boxes into the loop. When they meet, slow has walked a + b and fast has walked twice that, and the difference is some whole number of loops:

2(a + b) − (a + b) = a + b = kL, so a = kL − b

So walking a more boxes from the meeting point lands exactly on the loop start (going b boxes back to the start of the loop and then k full loops), and walking a boxes from the head also lands on the loop start. Two pointers walking a steps at the same speed therefore meet there.

On a straight chain the same two speeds give a bonus: when fast hits the end, slow is at the middle box, since it has walked half as far.

Why it is fast

Slow walks at most a + L boxes before the meeting, and the second phase walks a more.

steps ≤ a + L + a ≤ 2n, so O(n) time with O(1) extra memory

The visited-list method is also O(n) time but needs O(n) memory; the two runners need two pointers.

How to recognise it in an interview

The cues are "cycle" in a linked list, "where does the cycle begin", "middle of the list", "is the list a palindrome" (find the middle, reverse the second half, compare), and any sequence defined by "apply this function again" where values must eventually repeat. Say: "Two pointers at different speeds meet inside a cycle and never need extra memory; the fast one reaching the end also drops the slow one at the middle."

Linked List Cycle is the example above. Middle of the Linked List is the straight-chain bonus. Happy Number treats "sum the squares of the digits" as the next arrow, so a loop that avoids 1 means the number is not happy.

02The idea in one line

Two speeds: a cycle makes them meet; otherwise slow lands on the middle.

Reach for it when: Cycle detection, cycle start, middle node, palindrome list, happy number.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

The video works one example: Cycle detection on 3→2→0→-4→(2). These are its captions in order, so you can follow without the video or check a step you missed.

1. Tortoise moves 1, hare moves 2: in a cycle the hare laps the tortoise
2. Step 1: slow → 2, fast → 0
3. Step 2: slow → 0, fast → 2
4. Step 3: both land on -4, they met → a cycle exists
5. To find the cycle start: reset one pointer to head, walk both at speed 1
6. Both advance one: 2 and 2 — they meet at the cycle start
7. Cycle begins at node 2
8. No extra memory, at most 2n steps: O(n) time, O(1) space

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Linked List: In-place reversal, Dummy head and splice, Digit-by-digit with carry, Clone with a map or interleaving.