Linked List · LC #141
Linked List Cycle
Detect whether a singly linked list contains a cycle using Floyd's two-pointer algorithm. O(n) time, O(1) space - no hash set required.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given head, the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle, otherwise return false.
Sample I/O
Input: 3 → 2 → 0 → -4 → (back to 2) Output: true Input: 1 → 2 → (no cycle) Output: false
Intuition
How to Think About It
Intuition
If two runners start at the same point on a circular track and one is faster, the fast runner will eventually lap the slow runner - they will meet. The same principle applies to a linked list with a cycle: a fast pointer (2 steps) will catch up to a slow pointer (1 step) if a cycle exists. If there is no cycle the fast pointer exits the list.
Core Concept
Initialise both slow and fast at head. Each iteration: slow moves one step, fast moves two steps. If slow === fast at any point, a cycle exists. If fast or fast.next becomes null, the list is acyclic. The mathematical guarantee is that within at most 2n steps the pointers meet inside the cycle. Time: O(n), Space: O(1).
When to use
Cycle detection in linked lists; also serves as the first step in finding the cycle entry point (LC #142) or the middle of a list.
When NOT to use
When you also need to know which node starts the cycle - use the extended Floyd's algorithm (LC #142). If memory is not a constraint a visited hash set is simpler to implement.
Key Insights
What to Know Cold
- Floyd's algorithm (tortoise and hare) guarantees meeting within the cycle, not necessarily at the cycle entry.
- Must check fast != null AND fast.next != null before advancing to avoid null-pointer exceptions.
- The hash-set approach is O(n) space but often easier to reason about in a first pass.
- For cycle entry point: after meeting, reset one pointer to head and advance both one step at a time - they meet at the entry.
- A list with a single self-loop (node.next = node) is correctly detected on the first iteration.
1 example
Worked Examples
Cycle detection on 4-node list
3→2→0→-4 with -4 pointing back to 2
Floyd's slow/fast pointer
function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Output: true
Core pattern for cycle problems; reused in Find Duplicate Number (LC #287) and Circular Array Loop.