Linked List Cycle
Decide whether a linked list loops back on itself, using a slow and a fast pointer (or a set of visited nodes).
- Fast and slow pointers
- Floyd's cycle detection
Before this, know: What a linked list is (see the week 4 overview), Hash sets (week 1)
You get head, the first node of a linked list. Normally the last node’s next
is null, so walking the list eventually stops. But in a broken list, the last
node may point back to an earlier node, forming a cycle (a loop): walking
it would go round forever.
Return true if the list has a cycle, false if it doesn’t.
How LeetCode describes the input: head = [3, 2, 0, -4], pos = 1. pos is the
index the tail links back to (-1 means no cycle). Careful: your function never
sees pos. It only gets head, and must discover the loop by walking.
The rules that matter:
- The list can be empty, a single node, or a single node pointing to itself.
- Values can repeat, so “I’ve seen this value before” proves nothing. Only “I’ve stood on this exact node before” does.
- Follow-up: can you do it with O(1) memory?
So: send two pointers down the list, slow moving 1 node per turn and fast
moving 2. If fast ever reaches null, the list has an end: no cycle. If slow
and fast ever land on the same node, there’s a loop.
Once both are inside the loop, measure the gap: how many steps the hare is behind the tortoise, going round the loop. Each turn the tortoise moves 1 and the hare moves 2, so the hare gains exactly 1 step. The gap goes down by exactly 1 each turn: 3, 2, 1, 0. It can’t skip from 1 to −1, because it only ever shrinks by 1. When it hits 0 they’re on the same node.
Pause and think
The gap shrinks by 1 per turn: 4 → 3 → 2 → 1 → 0. They meet after 4 turns.
The gap is always smaller than the loop length (5), so they meet in fewer than 5 turns, before the tortoise finishes even one lap. That’s why the whole algorithm is O(n): the tortoise walks at most about n nodes.
Walk the list and keep a hash set of the nodes we’ve stood on (a set stores
items and answers “is this in here?” in about one step). If we ever arrive at a
node that’s already in the set, we’ve gone round a loop. If we reach null, there’s
no loop. The set stores nodes (their identity), not values, so repeated values
don’t confuse it.
Hash set of visited nodes
head = [3, 2, 0, -4], pos = 1 (the tail links back to index 1)
- node
- 3node
- result
- —
look up #0 (3): not found
- empty
- Standing here now
- In the set
- Just added
- Seen before: loop!
Is node #0 (3) in the set? No, first visit.
Which line is running?
function hasCycle(head) { const seen = new Set(); // the nodes we have already stood on let node = head; while (node !== null) {Running now: if (seen.has(node)) return true; // been here before: we are going round a loop seen.add(node); node = node.next; } return false; // we fell off the end, so there is no loop}Hash set of visited nodes
function hasCycle(head) { const seen = new Set(); // the nodes we have already stood on let node = head; while (node !== null) { if (seen.has(node)) return true; // been here before: we are going round a loop seen.add(node); node = node.next; } return false; // we fell off the end, so there is no loop}def has_cycle(head): seen = set() # the nodes we have already stood on node = head while node is not None: if node in seen: return True # been here before: we are going round a loop seen.add(node) node = node.next return False # we fell off the end, so there is no loopThis one is actually fast: O(n) time, one visit per node. The problem is memory: the set grows to hold every node, O(n) extra space. For 10,000 nodes, 10,000 set entries. The follow-up asks for O(1) memory, and the hash set can’t do that.
This technique is called Floyd’s cycle detection, or “the tortoise and the hare”. Two pointers walk the same list at different speeds; how they end up tells you about the list’s shape (a loop, the middle, and more).
Pattern
Fast and slow pointers
Use it when: you need to detect a loop, find the middle, or find where a cycle starts, with O(1) extra memory.
Signal words
- “cycle”
- “loop”
- “middle of the linked list”
- “O(1) memory”
- “happy number”
- “duplicate number”
- Start
slowandfastathead. - While
fastandfast.nextboth exist (so the hare can take 2 steps): - Move
slowone node andfasttwo nodes. - If
slowandfastare the same node, returntrue. - If the loop ends, the hare found the end of the list: return
false.
The shaded nodes form the loop (we can see it; the code can’t). Watch the gap in the variables panel once both pointers are in the loop. It’s measured at the end of each turn, after the hare moves (that’s when the code compares), and it drops by one every turn until it hits 0 and they meet. In the middle of a turn, after only the tortoise has moved, the panel still shows last turn’s gap. In the LeetCode example the tortoise even lands on the hare’s node mid-turn (turn 2): they share a node for a moment, but the code only compares after the hare moves, and by then the hare has moved on. Then try “No cycle”, where the hare runs off the end, and the edge cases.
Tortoise (slow) and hare (fast)
head = [3, 2, 0, -4], pos = 1 (the tail links back to index 1)
- slow
- 3node
- fast
- 3node
- turns
- 0
- gap
- —
- result
- —
- Nodes in the loop
- slow
- fast
- Where they meet
Both runners start at the head, node 3. slow (the tortoise) will move 1 node per turn, fast (the hare) 2 nodes per turn. The shaded nodes form the loop (we can see it; the code can't).
Which line is running?
function hasCycle(head) {Running now: let slow = head; // the tortoise let fast = head; // the hare while (fast !== null && fast.next !== null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps if (slow === fast) return true; // they met: there is a loop } return false; // the hare reached the end: no loop}Tortoise and hare
function hasCycle(head) { let slow = head; // the tortoise let fast = head; // the hare while (fast !== null && fast.next !== null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps if (slow === fast) return true; // they met: there is a loop } return false; // the hare reached the end: no loop}def has_cycle(head): slow = head # the tortoise fast = head # the hare while fast is not None and fast.next is not None: slow = slow.next # 1 step fast = fast.next.next # 2 steps if slow is fast: return True # they met: there is a loop return False # the hare reached the end: no loopThe line numbers match until line 7; Python then splits the return True onto its
own line. On LeetCode the Python method is def hasCycle(self, head) in class Solution.
- Lines 2–3: both runners start at the head.
- Line 4: the hare is about to take two steps:
fast.next, thenfast.next.next. Bothfastandfast.nextmust exist, or we’d read.nextofnulland crash. If either is missing, the list ends: no cycle. - Line 5: tortoise, one step. It never runs ahead of the hare, so if the hare
got here safely,
slow.nextis safe too. - Line 6: hare, two steps.
- Line 7:
===(JS) /is(Python) compares identity: the same node object, not just equal values. Two different nodes that both hold 2 aren’t a meeting. - Line 9: the loop ended because the hare hit the end, so there’s no cycle.
We check for a meeting after moving, not before: at the start both are on the head, which would count as a meeting by mistake.
head = [3, 2, 0, -4], pos = 1 (the loop is 2 → 0 → -4 → back to 2):
| turn | slow | fast | same node? | gap (hare behind) |
|---|---|---|---|---|
| start | 3 | 3 | (not checked) | — |
| 1 | 2 | 0 | no | 2 |
| 2 | 0 | 2 | no | 1 |
| 3 | -4 | -4 | yes → return true | 0 |
Each row is the state at the end of a turn, after the hare has moved. From turn 1 both are inside the loop (3 nodes long). The gap goes 2, 1, 0: one smaller every turn, exactly as promised.
Hash set of nodes
Time
O(n)
Each node is visited once (plus one repeat visit if there's a loop).
Space
O(n)
The set ends up holding every node.
Tortoise and hare
Time
O(n)
Without a loop, the hare reaches the end in n/2 turns. With one, the tortoise enters the loop within n turns and is caught before finishing one lap.
Space
O(1)
Two pointers, whatever the list's length.
What to say out loud:
- “A hash set of visited nodes works in O(n) time but O(n) space.”
- “For O(1) space I’ll use a slow and a fast pointer.”
- “If there’s no loop, fast reaches null. If there is one, fast gains one step per turn, so the gap shrinks to zero and they meet.”
- “Compare node identity, and check fast and fast.next before jumping.”
Likely follow-ups:
- “Where does the cycle start?” (Linked List Cycle II, LeetCode 142) After they meet, put one pointer back at the head and move both one step at a time; where they meet again is the start of the loop.
- “How long is the loop?” After meeting, keep one pointer still and count steps until the other comes back round.
Related problems:
- Find the Duplicate Number (LeetCode 287, week 5 of the roadmap): the same tortoise and hare, on an array treated as a linked list.
- Reorder List: slow and fast pointers find the middle.
- Happy Number (LeetCode 202): a “cycle” of numbers, detected the same way.