Linked List Cycle
Understand the problem
Given the head of a linked list, return true if the list has a cycle — that is, some node can be reached again by following next pointers continuously.
ts
// 3 → 2 → 0 → -4
// ↑_________| (-4.next points back to node 2) → true
// 1 → 2 → null → falseWith a cycle, walking next runs forever.
- The classic trick: two pointers moving at different speeds (fast and slow).
- If there is a cycle, the fast pointer will "catch up" with the slow pointer inside the loop.
Basic approach
O(n) time, O(n) spacets
function hasCycleSet(head: ListNode | null): boolean {
const seen = new Set<ListNode>()
for (let node = head; node; node = node.next) {
if (seen.has(node)) return true // revisited a node → cycle
seen.add(node)
}
return false // hit null → list has an end, no cycle
}Why this approach is slow:
This approach stores every visited node in a Set to detect a repeat.
It is correct but uses O(n) memory; the fast and slow pointer technique gets the same O(n) time with only O(1) memory.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.