Linked List Cycle
A fast pointer laps a slow one if and only if there's a loop.
Floyd's Pointer Race
Problem
Given the head of a singly linked list, determine whether repeatedly following next eventually revisits a node. Return true when the list loops back to an earlier node; otherwise return false when traversal reaches null.
Examples
Input: head = [3,2,0,-4], pos = 1
Output: true
2, so traversal cycles through 2 → 0 → -4.Input: head = [1,2], pos = -1
Output: false
null, so the traversal terminates.The Goal
Return True if following next from the head ever comes back to a node it already passed, and False if it reaches None.
In the example, the tail links back to the node holding 2, so the walk goes 3 → 2 → 0 → -4 → 2 → … forever.
Compare nodes, not values. Two different nodes can hold the same number without any cycle.
Follow links, not values
A cycle is a next link back to a node the walk already passed. Equal values prove nothing: [1, 2, 1] can be three different nodes.
Check whether slow and fast are the same node.
Key Idea: A Race on a Track
Send two pointers from the head. slow moves one node a step, and fast moves two.
Without a cycle, fast reaches the end first. With one, both end up going round the loop. There, fast gains one node on slow every step, so the gap closes to zero within one lap and they land on the same node.
You keep two pointers and no record of the nodes visited.
fast gains one node on slow every step, so the gap shrinks to zero.
They land on -4 after three steps.
The Algorithm
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 FalseThe loop checks fast and fast.next before taking two steps, so it never reads past None. It compares after both pointers move. They start on the same node, so comparing first would report a cycle in every list.
| Approach | Time | Extra space | How |
|---|---|---|---|
| Slow and fast pointers | O(n) | O(1) | Two pointers race |
| Set of visited nodes | O(n) | O(n) | Remembers every node it passes |
Walkthrough
Run it on 3 → 2 → 0 → -4, with the tail linked back to 2.
After one step, slow is on 2 and fast is on 0. After two, slow is on 0 and fast has gone round the loop to 2. After three, both land on -4, and the code returns True.
Try Break it. With no cycle, fast reaches the end and the answer is False.
Checkpoint · predict the next step
Step 3 of 8 on the stage: fast takes two steps, through 2 to 0. It hasn't landed on slow.
slow on 2 · fast on 0 · links 3→2, 2→0, 0→-4, -4→2 · steps 1
Pitfalls
- Check
fast and fast.nextbeforefast.next.next. Otherwise a list without a cycle crashes at its end. - Compare after moving, not before. Both pointers start on the head.
- Use
is, not==. Equal values aren't the same node. - An empty list, or one node with no link back, returns
False. One node linked to itself returnsTrue.
Which loop is safe and compares at the right time?
Complexity
Without a cycle, fast reaches the end in about n / 2 steps. With one, slow reaches the loop within n steps, and fast catches it before slow finishes one lap. Either way, time is O(n).
Only slow and fast are kept, so extra space is O(1). A set of visited nodes is also O(n) time, but O(n) space.
Two pointers, one race
- Move slow and fastConstant work a step.dominantO(n)
- Compare the nodesAn identity check.O(1)
- slow and fastTwo pointers, whatever the length.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear time, and no memory of where the pointers have been.
In short
Advance one pointer by one and another by two each step. If they ever meet, there's a cycle; if the fast pointer reaches the end, there isn't. Floyd's trick detects loops in O(1) space, unlike a visited-set approach.
Common mistake
Checking pointer identity before advancing, or not guarding fast.next before taking two steps.