Fast & Slow Pointers

Lesson 3 of 7 in Core Patterns · 25 min · Intermediate

A hare and a tortoise: if there's a loop, they meet.

Introduction

Two runners start together on a track you can't see. One runs twice as fast as the other. If you only watch whether the fast one ever catches the slow one, can you tell that the track is a loop?

On a straight road, the fast runner pulls away and never looks back. Nobody gets passed twice, and the fast runner reaches the finish line while the slow one is still halfway there.

Now bend the road into a circle. The fast runner has no finish line. It keeps coming up behind the slow runner and, sooner or later, the two stand on the same spot. What does that meeting prove?

Lesson overview

This lesson will show you how to:

Explain why a fast and slow pointer can only meet on a loop.
Trace Floyd's cycle check on a linked list that loops back.
Find the middle node of a list in one pass, without its length.
Locate where a cycle begins by resetting one pointer to the head.
Spot repeated sequences, like Happy Number, that hide a linked list.

The picture

Linked list: 3 → 2 → 0 → -4 → 7 → back to 0 (a loop). Pointers: slow at 2; fast at -4.

Picture a tortoise and a hare starting together. The hare takes two steps for each of the tortoise's one. On a straight road the hare reaches the end first and the race is over, but on a loop it comes round behind the tortoise and catches it.

You never need a map of the track. Whether the two ever meet, and where the slow one is when the fast one runs out, tells you its shape.

Two pointers at different speeds can only meet again on a loop, and when the fast one runs off the end, the slow one is halfway.

Words to know

slow and fast pointers: Two pointers that start together on the head. slow moves one node per lap and fast moves two. Also called the tortoise and the hare.
cycle: A stretch of the list that loops: following next links brings you back to a node you already visited, so you never reach null.
Floyd's algorithm: The tortoise-and-hare method. Phase 1 races slow and fast to see whether they meet. Phase 2 restarts one pointer at the head to find where the loop begins.
meeting point: The node where slow and fast first stand together. It is always inside the cycle, but not always at its start.
cycle entry: The first node of the loop: the node the tail's link points back to. It is where the straight part of the list ends and the loop begins.
middle node: The node halfway along the list. With an even number of nodes there are two middles, and LeetCode 876 (and this lesson) returns the second one.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

Yes: A linked list might loop back on itself, and you must say whether it does.
Yes: You need the middle of a list in one pass, without knowing its length.
Yes: Each value tells you where to go next (a next index, a digit-square sum) and the sequence may repeat forever.
Yes: The problem asks for O(1) extra space, so remembering every node you visited is not allowed.

Not this when

No: You have an array and want its middle: just read index n // 2. No pointers needed.
No: You need to know whether a value was seen before, and memory is fine: a hash set answers it directly.
No: You need the k-th node from the end: a pointer k steps ahead of the other fits better, and that is plain two pointers.

Which pattern fits?

Which pattern? 1 of 5
Given the head of a linked list, decide whether the list contains a cycle, using only O(1) extra space.
Which pattern? 2 of 5
Given an unsorted array of numbers and a target, return the indices of the two numbers that add up to the target.
Which pattern? 3 of 5
Given the head of a singly linked list, reverse it in place and return the new head.
Which pattern? 4 of 5
Replace a number by the sum of the squares of its digits, again and again. Does it reach 1, or loop forever? Do it without storing every number seen.
Which pattern? 5 of 5
Given a sorted array and a target, find two numbers that add up to it.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode

1slow = head, fast = head
2while fast and fast.next exist:
3slow takes 1 step, fast takes 2 steps
4if slow and fast are the same node:
5return true (they met, so there is a cycle)
5return false (fast ran out, so there is no cycle)

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Time · O(n)Space · O(1)

slow takes at most n steps before the pointers meet or fast runs out, so the loop is O(n). Only two pointers are stored, so the space is O(1).
A hash set also detects a cycle: add each node as you visit it, and a node already in the set means a loop. That is O(n) time but O(n) space, because it remembers every node. Fast and slow pointers give the same answer with no memory.
Test fast before fast.next. If fast is null, asking for fast.next would crash, so the loop condition checks both.
For the middle (LeetCode 876), drop the meet test and return slow when the loop ends. With two middles this returns the second. To get the first, loop while fast.next and fast.next.next exist.
For the cycle start (LeetCode 142), after they meet put slow back on the head and move both one step at a time. If the entry is a steps from the head and they met b steps past it, slow walked a + b and fast walked 2(a + b), so a + b is a whole number of laps. That makes a the same distance as from the meeting point on to the entry, give or take whole laps.
It works on any sequence where each value tells you the next, not only lists: Happy Number (202) and Find the Duplicate Number (287) hide a linked list inside numbers.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode

Given the head of a linked list, return true if the list has a cycle: some node can be reached again by following next pointers. Otherwise return false.

Input

head = [3,2,0,-4], pos = 1 (the tail links back to index 1)

Output

true

Approach

Start slow and fast on the head. Each lap slow takes 1 step and fast takes 2.
If the list ends, fast reaches null before slow does, so return false.
On a loop, fast gains exactly one node on slow each lap, so it cannot jump over slow. Sooner or later they stand on the same node.
In [3,2,0,-4] with the tail linked back to index 1, they meet on -4 after three laps, so return true.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

On a loop, why can fast never jump over slow without landing on it?
Why does the loop read `while fast and fast.next` instead of only `while fast`?
You run the middle-node loop on the list 10, 20, 30, 40. Which node does it return?
In phase 2 of Floyd's algorithm, slow returns to the head and both pointers move one step at a time. Why do they meet on the cycle entry?
A hash set can also detect a cycle: remember every node you visit and stop when you see one twice. What do fast and slow pointers do better?

Question 1 of 5

On a loop, why can fast never jump over slow without landing on it?

Each lap fast gains exactly one node on slow, so the gap shrinks by one at a time and reaches zero instead of skipping past it.fast is always exactly one full lap ahead of slow.The list is sorted, so fast has to stop at slow's value.slow steps backwards whenever fast gets close.

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 7 solved

Solve Happy Number (opens in a new tab) (LeetCode, easy)
Hint: Replacing a number by the sum of its digit squares gives each number a single next number. That sequence either reaches 1 or loops, so race two runners over it.
Solve Palindrome Linked List (opens in a new tab) (LeetCode, easy)
Hint: Fast and slow find the middle in one pass. Then ask what you could do to the second half so that it can be compared with the first.
Solve Delete the Middle Node of a Linked List (opens in a new tab) (LeetCode, medium)
Hint: To delete a node you must stand on the one before it. Where does slow end up if fast starts a little ahead, or if you stop the loop sooner?
Solve Reorder List (opens in a new tab) (LeetCode, medium)
Hint: It combines three moves you know: find the middle, reverse the second half, then weave the two halves together.
Solve Find the Duplicate Number (opens in a new tab) (LeetCode, medium)
Hint: Treat each value as a pointer to the index with that number. Two different indices pointing at the same place make a cycle, and the duplicate is where the cycle starts.
Solve Circular Array Loop (opens in a new tab) (LeetCode, medium)
Hint: Each index jumps by its value, so the array is a hidden linked list. Look out for loops that change direction and loops of length one, which don't count.
Solve Remove Nth Node From End of List (opens in a new tab) (LeetCode, medium)
Hint: Two runners that don't need different speeds, only a gap. If one starts n nodes ahead, where is the other when the leader runs out of list?

Additional resources

Cycle detection (opens in a new tab) — Tortoise-and-hare explained, with the meeting point and cycle-start reasoning.
Floyd's cycle-finding algorithm (opens in a new tab) — The original two-pointer method, with its constant-memory advantage over hash sets.