Fast & Slow — Linked List Cycle
↗ LeetCode: Linked List Cycle · Easy · pattern chapter →
Given the head of a linked list, return true iff the list contains a cycle.
Example 1 — head = [3,2,0,-4], tail connects to index 1 → trueExample 2 — head = [1,2], tail connects to index 0 → trueExample 3 — head = [1], tail = null → false
Constraints — 0 ≤ n ≤ 10⁴. Brute is O(n) time + O(n) memory with a visited HashSet — GC pressure adds ~10⁶ ns overhead per node. Floyd's tortoise & hare is O(n) time + O(1) space — half a dozen pointer chases per node.
Interview timer00:00
Approach 1 — Hash set of visited nodes
Intuition. Walk the list; if a node reference reappears in the set, cycle found.
boolean hasCycleHash(ListNode head) {
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (!seen.add(head)) return true;
head = head.next;
}
return false;
}Complexity — Time O(n); Space O(n).
Approach 2 — Floyd's tortoise and hare (canonical)
Insight from hash. We don't need to store visited nodes; two pointers at different speeds will meet inside a cycle. slow advances 1; fast advances 2. If they ever meet, cycle exists. If fast hits null, no cycle.
Why they meet. Once both pointers are in the cycle, fast gains 1 step per iteration on slow. In a cycle of length L, fast catches up in ≤ L steps.
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}Complexity — Time O(n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Hash set | O(n) | O(n) | acceptable |
| Floyd's tortoise/hare | O(n) | O(1) | expected optimum |
When to use which
- Ship this → Floyd's algorithm.
- "Return the cycle entry node" → Floyd + reset one pointer to head (see Linked List Cycle II).
- "Return cycle length" → after
slow == fast, walkfastaround the loop until it meetsslowagain — length = steps taken. - Modifying list allowed? → some variants mark visited nodes; not standard.
Related problems
- Linked List Cycle II — return entry node
- Happy Number — cycle detection on integer sequence
- Find the Duplicate Number — cycle detection on array as implicit list