/Projects
Coding patterns · 03 of 15

Fast and slow pointers

One pointer moves twice as fast; they meet in a cycle.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot fast and slow pointers from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(n) time, O(1) space Watch as reels
Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

Move slow by one and fast by two. A cycle makes them meet; fast reaching the end proves none exists. When fast finishes, slow is in the middle.

Why it works

If a list loops, a pointer moving two steps gains one step per move on a pointer moving one step, so inside the loop it must land on it. Without a loop, the fast pointer simply reaches the end. Floyd's second phase works because the distance from the head to the cycle's start equals the distance from the meeting point to the start, going round the loop.

Typical cost: O(n) time, O(1) space

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Linked list cyclesMiddle of a listSequences that may loop (happy number)Find the duplicate with O(1) space
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Linked List Cycle II

The problem statement, then the plan you would say out loud.

Problem

Return the node where the cycle begins, or null.

Plan before you code

  1. Find a meeting point with fast and slow.
  2. Reset one pointer to head.
  3. Move both one step at a time; they meet at the cycle start (distance maths).
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

Detect a cycle

detect-cycle.tsTypeScript
1type ListNode = { val: number; next: ListNode | null };2 3function hasCycle(head: ListNode | null): boolean {4  let slow = head, fast = head;5  while (fast && fast.next) {6    slow = slow!.next;7    fast = fast.next.next;8    if (slow === fast) return true;9  }10  return false;11}
11 linesUTF-8TypeScript
  1. Both pointers start at the head.
  2. Slow moves one step, fast moves two.
  3. If they ever meet, the list loops.

3.2Solution

Strict TypeScript, type-checked and tested.

Linked List Cycle II

linked-list-cycle.tsTypeScript
1function detectCycle(head: ListNode | null): ListNode | null {2  let slow = head, fast = head;3  while (fast && fast.next) {4    slow = slow!.next;5    fast = fast.next.next;6    if (slow === fast) {7      let p = head;8      while (p !== slow) {9        p = p!.next;10        slow = slow!.next;11      }12      return p;13    }14  }15  return null;16}
16 linesUTF-8TypeScript

Step by step

  1. Race: slow moves one step, fast moves two.
  2. Meeting proves a cycle.
  3. Restart one pointer at head; step together; they meet at the cycle start.

Complexity: O(n) time, O(1) space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

Why not store visited nodes in a set?
That works in O(n) time but needs O(n) memory. Fast and slow pointers use O(1) memory, which is usually what the question is testing.
How do you find the middle of a list?
Move slow one step and fast two. When fast reaches the end, slow is at the middle.
Why is Find the Duplicate a cycle problem?
Treat index → value as a next pointer. Two indices point at the duplicate value, so that node has two incoming arrows: the entrance of a cycle.

4.2Solo practice

Try these without looking; open the hint only when stuck.

EasyMiddle of the Linked List
Hint

When fast ends, slow is the middle.

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Easy

Happy Number

Repeatedly replace n with the sum of squares of its digits. Does it reach 1?

  1. The sequence either reaches 1 or loops.
  2. Detect the loop with fast and slow pointers, without storing a set.
happy-number.tsTypeScript
1function isHappy(n: number): boolean {2  const step = (x: number) =>3    [...String(x)].reduce((sum, d) => sum + Number(d) ** 2, 0);4  let slow = n, fast = step(n);5  while (fast !== 1 && slow !== fast) {6    slow = step(slow);7    fast = step(step(fast));8  }9  return fast === 1;10}
10 linesUTF-8TypeScript

Complexity: O(log n) per step, O(1) space

Medium

Find the Duplicate Number

n + 1 numbers in [1, n], one repeated. Find it in O(1) extra space without changing the array.

  1. Treat i → nums[i] as a linked list; the duplicate value is where two arrows enter one node.
  2. That makes a cycle; its entrance is the duplicate.
  3. Use Floyd's algorithm.
find-duplicate-number.tsTypeScript
1function findDuplicate(nums: number[]): number {2  let slow = nums[0], fast = nums[0];3  do {4    slow = nums[slow];5    fast = nums[nums[fast]];6  } while (slow !== fast);7  slow = nums[0];8  while (slow !== fast) {9    slow = nums[slow];10    fast = nums[fast];11  }12  return slow;13}
13 linesUTF-8TypeScript

Complexity: O(n) time, O(1) space

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Checking fast.next.next without checking fast.next
  • Comparing values instead of node identity
AI Engineer · Fast and slow pointers