---
title: "Fast and slow pointers: cycle detection and the middle of a list in O(1) space"
url: https://algopath.pro/blog/fast-and-slow-pointers
language: en
summary: "Two pointers at speeds one and two find a cycle, its start, and the middle node without extra memory. The wording that calls for it, Python code, the proof, and Find the Duplicate Number."
updated: 2026-09-30
---

# Fast and slow pointers: cycle detection and the middle of a list in O(1) space

**Short answer.** Fast and slow pointers walk the same list at different speeds. The slow one moves one step, the fast one moves two. If they ever meet, the list has a cycle. The same trick finds the middle of a list in one pass. Below: the trigger words, Python code, and the cycle start proof.

 

## What are fast and slow pointers?

 

You keep two references into a linked list. Both start at the head. Each step, slow advances by one node and fast by two.

 

Without a cycle, fast reaches the end first. With a cycle, fast laps slow. They land on the same node.

 

The pattern is also called Floyd's tortoise and hare. It needs O(1) extra memory. That is its whole point.

 

## When does a problem need fast and slow pointers?

 

- "Detect a cycle" in a linked list, without extra memory.
- "Find the middle node" in one pass.
- "Is this number happy" or any sequence that may loop.
- "Find the duplicate number" where the array holds values in 1..n.

 

The common signal is a sequence you can only walk forward. There is no index to jump to. A hash set works too, but it costs O(n) memory. Interviewers ask for the O(1) version.

 

## How do fast and slow pointers find the middle?

 

Move slow by one and fast by two. Stop when fast hits the end. Slow now sits on the middle node.

 

With an even length there are two middles. This code returns the second one. Stop fast one node earlier to get the first.

 

```
class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    slow = head
    while slow is not fast:
        slow, fast = slow.next, fast.next
    return slow
```

 

## Why does the cycle start trick work?

 

Call the distance from head to the cycle start a. Call the cycle length c. When the pointers meet, slow has walked a + k steps. Fast has walked twice that.

 

The difference between them is a whole number of laps. So a + k is a multiple of c. Move one pointer back to the head. Walk both at speed one. After a steps, the pointer from the head reaches the start. The other one has walked a more steps inside the cycle. It also lands on the start.

 

## How do fast and slow pointers compare with a hash set?

 

| Approach | Time | Memory | Finds cycle start |
| --- | --- | --- | --- |
| Hash set of visited nodes | O(n) | O(n) | Yes, first repeated node |
| Fast and slow pointers | O(n) | O(1) | Yes, with the second phase |
| Marking nodes in place | O(n) | O(1) | Yes, but it mutates input |

 

Pick the hash set when memory is allowed. It is the shortest code. Pick two pointers when the interviewer says O(1) space.

 

## How does the pattern solve Find the Duplicate Number?

 

An array of n + 1 integers holds values from 1 to n. One value repeats. You may not modify the array or use extra memory.

 

Treat each value as a pointer: index i points to index nums[i]. Two indexes point to the same place. So the walk has a cycle. The duplicate is the cycle start. Run the cycle start code on this walk.

 

## What mistakes break fast and slow pointers?

 

- Checking only fast and not fast.next before taking two steps. That raises on a list of odd length.
- Comparing values with == instead of nodes with is. Two nodes can hold the same value.
- Starting fast at head.next. The proof above assumes both start at head.
- Forgetting the empty list. Return early when head is None.

 

## How do you explain fast and slow pointers in an interview?

 

Name the constraint first: O(1) memory. Say the speeds: one and two. State the fact: in a cycle, fast catches slow within one lap. Then write the loop.

 

If asked for the cycle start, say "second phase, reset one pointer to the head". Give the a + k argument in two sentences. That is enough.

 

Drill the pattern on the [fast and slow pointers](/patterns/fast-slow-pointers) page. The full list of patterns is in [LeetCode patterns](/blog/leetcode-patterns).

 

## FAQ

 

### Why speed two and not three?

 

Any speed above one works for detection. Two keeps the proof simple and the walk short. Speed three may take longer to meet inside a short cycle. It still meets.

 

### Does the pattern work on arrays?

 

Yes, whenever a value can be read as the next index. Find the Duplicate Number is the classic case.

 

### Can fast and slow pointers find the k-th node from the end?

 

That is a different two-pointer trick. Both move at speed one. A gap of k nodes sits between them. Same family, different rule.