Linked List Cycle II
Find the node where a cycle in a linked list begins, using fast and slow pointers and O(1) extra space, with a proof of why the method works.
Updated Medium read: 7 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Hash set of visited nodes | O(n) | O(n) |
| Fast and slow pointers | O(n) | O(1) |
The problem
A linked list normally ends with a node whose next is null. In a list with a cycle, the last node points back to an earlier node instead, so following next goes round for ever.
Given the head of a list, return the node where the cycle begins: the first node that would be visited twice. If there is no cycle, return null. The list must not be modified.
3 → 2 → 0 → -4
↑ │
└────────┘ → the node holding 2
1 → 2
↑ │
└───┘ → the node holding 1
1 → null → null (no cycle)The answer is a node, not a value or a position. Two different nodes can hold the same value.
A node, in each language. All the code on this page uses this shape:
JavaScript
// A node is any object with a value and a next.
const node = { value: 1, next: null };Python
class ListNode:
def __init__(self, value, next=None):
self.value = value
self.next = nextApproach 1: hash set of visited nodes
Walk the list, remembering every node passed. The first node that is already in the set is where the cycle begins. Reaching null means there is no cycle.
JavaScript
function detectCycleWithSet(head) {
const visited = new Set();
for (let node = head; node !== null; node = node.next) {
if (visited.has(node)) return node;
visited.add(node);
}
return null;
}Python
def detect_cycle_with_set(head):
visited = set()
node = head
while node is not None:
if node in visited:
return node
visited.add(node)
node = node.next
return NoneThe set stores the node objects themselves, so two nodes with equal values are still told apart.
Time O(n). Space O(n) for the set. It is simple and correct; the challenge is to do without the extra memory.
Approach 2: fast and slow pointers
This uses the first technique from the linked list pointers pattern, in two phases.
Phase 1: find out whether there is a cycle. Start two pointers at the head. Move slow one node at a time and fast two. If fast reaches the end, there is no cycle. If there is a cycle, fast goes round it and eventually lands on slow.
Phase 2: find where the cycle begins. Leave slow at the meeting point. Start a new pointer at the head. Move both one node at a time. The node where they meet is the start of the cycle.
JavaScript
function detectCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let finder = head;
while (finder !== slow) {
finder = finder.next;
slow = slow.next;
}
return finder;
}
}
return null;
}Python
def detect_cycle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow is fast:
finder = head
while finder is not slow:
finder = finder.next
slow = slow.next
return finder
return NonePhase 1 is easy to believe. Phase 2 looks like a coincidence until the distances are written down.
Walkthrough
3 → 2 → 0 → -4, with -4 pointing back to 2:
| Phase | Step | slow | fast | finder |
|---|---|---|---|---|
| 1 | Start | 3 | 3 | |
| 1 | 1 | 2 | 0 | |
| 1 | 2 | 0 | 2 | |
| 1 | 3 | -4 | -4 | They meet |
| 2 | Start | -4 | 3 | |
| 2 | 1 | 2 | 2 |
In the third step of phase 1, fast goes from 2 to 0 to -4 and lands on slow. In phase 2, one step takes finder from 3 to 2 and slow from -4 round to 2. They meet on the node holding 2, which is the answer.
Time O(n): slow meets fast before completing its first lap of the cycle, and phase 2 takes no more steps than the distance from the head to the cycle. Space O(1).
Why phase 2 works
Give the distances names, counted in steps:
head ──── a ────→ cycle start ──── b ────→ meeting point
↑ │
└──── rest of cycle ─────┘
a = from the head to the start of the cycle
b = from the start of the cycle to the meeting point
c = the length of the whole cycleWhen the pointers meet:
slowhas takena + bsteps.fasthas taken twice as many:2(a + b).
Both are standing on the same node, and fast got there by going round the cycle some whole number of extra times. So the difference between their distances is a whole number of laps:
2(a + b) − (a + b) = a + b = (some whole number) × cIn words: walking a + b steps from the start of the cycle brings you back to the start of the cycle.
Now look at where slow is: b steps past the start of the cycle. If it walks another a steps, it will have gone a + b steps past the start in total, which by the line above puts it exactly back on the start.
And a is also the distance from the head to the start of the cycle. So a pointer leaving the head and a pointer leaving the meeting point, both moving one step at a time, arrive at the start of the cycle after exactly a steps, at the same moment. That is where they meet.
Checking with the walkthrough: a = 1 (from 3 to 2), b = 2 (from 2 to -4) and c = 3. Indeed a + b = 3, one whole lap.
Why the pointers must meet in phase 1
Once both pointers are inside the cycle, think of fast as chasing slow. Each step, fast moves two nodes and slow moves one, so the gap between them closes by exactly one. A gap that shrinks by one each step cannot skip past zero. fast never jumps over slow.
Try it yourself
Copy a solution from above, add the lines below, and run it. The Python version also needs the ListNode class from the top of the page. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
const a = { value: 3, next: null };
const b = { value: 2, next: null };
const c = { value: 0, next: null };
const d = { value: -4, next: null };
a.next = b;
b.next = c;
c.next = d;
d.next = b; // the last node points back to b
console.log(detectCycle(a).value); // 2
console.log(detectCycle({ value: 1, next: null })); // nullPython
a, b, c, d = ListNode(3), ListNode(2), ListNode(0), ListNode(-4)
a.next = b
b.next = c
c.next = d
d.next = b # the last node points back to b
print(detect_cycle(a).value) # 2
print(detect_cycle(ListNode(1))) # NoneThe comment after each line is the result you should see.
Common mistakes
- Comparing values instead of nodes.
slow.value === fast.valuegives false matches whenever two nodes hold the same value. Compare the nodes:slow === fast. - Checking only
fast !== null.fasttakes two steps, sofast.nextmust exist too, or the second step readsnextofnull. - Comparing before moving. Both pointers start on the head, so a check at the top of the loop reports a meeting immediately. Move first, then compare.
- Moving
slowtwo steps in phase 2. Both pointers move one step at a time in the second phase. The proof depends on it. - Returning the meeting point. The pointers usually meet somewhere inside the cycle, not at its start. Phase 2 is not optional.
Original problem: LeetCode 142: Linked List Cycle II