Linked Lists

Fast & Slow Pointers

Two pointers at different speeds to find cycles, middles and k-th from the end.

Medium, about 60 minutes to practise.

1Understand

The idea

Move one pointer twice as fast as the other. When the fast one reaches the end, the slow one is at the middle; if the list has a cycle, the fast one eventually laps the slow one and they meet. Starting one pointer k steps ahead finds the k-th node from the end in a single pass.

Intuition

Move one pointer twice as fast as the other. When the fast pointer reaches the end, the slow one is at the middle. If the list has a cycle, the fast one eventually laps the slow one and they meet.

Starting one pointer k steps ahead finds the k-th node from the end in a single pass, the gap stays constant as both walk.

Same idea detects cycles and then finds the cycle entrance by resetting one pointer to the head.

What you will be able to do

  • Guard fast.next before advancing
  • Reason about where the pointers meet

When to use it

  • Detect a cycle
  • Middle of the list
  • N-th node from the end in one pass

2See it

Walkthrough

Cycle detection

1 → 2 → 3 → 2 …, slow +1, fast +2 until they meet.

1 / 6

SF
1
2
3
↗2
0123
S → index 0F → index 0

List cycles 3→2. slow = fast = head. Compare references, not values.

slow = fast = head

Live template

Line 1 active

1slow = fast = head
2while fast and fast.next:
3 slow, fast = slow.next, fast.next.next
4 if slow is fast: return True

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

One pass O(n) time, O(1) space, better than counting length then walking again. Cycle detection is the same bound. Converting to an array is O(n) space and usually unnecessary.

Read the walkthrough as text

Middle of the list. 1 → 2 → 3 → 4 → 5.

  1. slow and fast start at 1.
  2. Each step: slow moves one, fast moves two.
  3. When fast lands on 5 (or its next is None), slow is on 3, the middle.

For even length 1..4, the usual convention lands slow on the second middle (3) or first (2) depending on the loop condition, match the problem statement.

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Cycle detection

    Example. Does a linked list have a cycle?

    How. Slow +1, fast +2; cycle ⇔ they meet before fast hits None.

  • Start of the cycle

    Example. Return node where the cycle begins.

    How. After meeting, reset one pointer to head; advance both by 1 until they meet again.

  • Middle node

    Example. Return middle of list (second middle if two).

    How. When fast reaches end, slow is at middle; stop when fast.next is None.

  • N-th from the end (gap pointers)

    Example. Remove n-th node from end in one pass.

    How. Advance fast n steps ahead; then move both until fast is past the last node.

  • Palindrome linked list

    Example. Is the list a palindrome (O(1) space)?

    How. Find middle, reverse second half, compare halves, optionally restore.

  • Cycle detection on an index-linked array (find the duplicate)

    Example. Array of n+1 values in 1..n, find duplicate.

    How. Treat index as node, value as next pointer; Floyd’s algorithm on the implicit graph.

  • Pointers that switch heads (list intersection)

    Example. Intersection node of two lists.

    How. Two walkers swap to the other head when they exhaust a list; they meet at intersection or None.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Null fast pointer

    Why it happens. Advancing fast twice without checking fast.next first.

    How it fails. fast = fast.next.next when fast.next is None, AttributeError on the last node.

    Fix. Loop condition `while fast and fast.next:` before advancing slow once and fast twice.

  • Extra memory

    Why it happens. A visited set detects cycles but ignores O(1) space requirements.

    How it fails. Cycle check with `seen`, correct answer but fails follow-up “constant memory”.

    Fix. Use Floyd: slow +1, fast +2; meeting inside the loop implies a cycle.

  • Wrong middle

    Why it happens. Fast stops one step early or late for even-length lists.

    How it fails. Even list: problem wants first middle but fast stops when fast.next is None, you return the second middle.

    Fix. Match the spec: `while fast and fast.next` → second middle; `while fast.next and fast.next.next` → first.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons