Fast/Slow Pointers — Linked List Cycle II
↗ LeetCode: Linked List Cycle II · Medium · pattern chapter →
Given the head of a linked list, return the node where the cycle begins, or null if no cycle.
Example 1 — 3→2→0→-4→(back to 2) → returns node 2Example 2 — 1→2→(back to 1) → returns node 1Example 3 — 1 (no next) → returns null
Constraints — 0 ≤ n ≤ 10⁴; O(1) extra space required for the follow-up. Brute stores every visited node in a HashSet — O(n) time but O(n) memory + hashing overhead. Floyd's tortoise & hare is O(n) time (~10⁶ pointer chases at max n) with O(1) extra memory — canonical since Floyd's 1967 paper.
Interview timer00:00
Approach 1 — Brute force (hash-set of visited nodes)
Intuition. Walk the list; store each node reference in a set; the first re-encountered node is the cycle entry.
ListNode detectCycleHash(ListNode head) {
Set<ListNode> seen = new HashSet<>();
for (ListNode cur = head; cur != null; cur = cur.next) {
if (!seen.add(cur)) return cur;
}
return null;
}Complexity — Time O(n); Space O(n) for the set.
Correct but the O(n) space is what most interviewers push back on.
Approach 2 — Floyd's tortoise and hare (O(1) space)
Insight from hash-set. Two pointers, one at 1x speed (slow) and one at 2x speed (fast), must collide inside the cycle if one exists (fast closes the gap by 1 per step). After a meeting, reset one pointer to head and advance both at 1x — they meet again exactly at the cycle entry.
Why the reset trick works. Let A = head → entry distance, C = cycle length, B = entry → meeting-point distance. When slow and fast meet: slow walked A+B, fast walked 2(A+B). The extra A+B fast walked is whole laps → A+B = kC → A = kC - B. So from the meeting point, walking A steps lands at the entry — exactly what the reset does.
ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // cycle proven
ListNode p = head;
while (p != slow) { p = p.next; slow = slow.next; }
return p; // entry
}
}
return null;
}Complexity — Time O(n); Space O(1). Optimal.
Trap. fast != null && fast.next != null — checking only fast != null NPEs on even-length lists like 1→2.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Hash set of visited nodes | O(n) | O(n) |
| Floyd tortoise & hare | O(n) | O(1) |
When to use which
- Cold interview → state hash-set, then Floyd for the O(1) space follow-up.
- Interviewer probes "why reset works" → the
A = kC − Bderivation.
Related problems (same ladder applies)
- Linked List Cycle (I) — return true/false, no entry needed
- Happy Number — Floyd on the digit-square-sum sequence
- Find the Duplicate Number — Floyd on
next = nums[i] - Palindrome Linked List — Floyd to find middle, reverse second half, compare