Linked List Cycle
Return true if the linked list contains a cycle.
- The number of the nodes in the list is in the range [0, 10⁴].
- -10⁵ <= Node.val <= 10⁵
- pos is -1 or a valid index in the linked-list.
Intuition
Linked list cycle asks whether a list loops back on itself. The straightforward answer stores every visited node in a hash set and reports a cycle when a node reappears — correct, O(n) time, O(n) space.
The constant-space answer is Floyd's cycle detection, and its argument is worth actually understanding rather than memorising:
- Move one pointer one node at a time and another two; if a cycle exists they must eventually meet.
The reason is that once both pointers are inside the loop, the fast pointer gains exactly one position on the slow one per step. The gap shrinks by one each iteration and cannot skip past zero — it must hit zero exactly. So a meeting is guaranteed, not merely likely.
If there is no cycle, the fast pointer runs off the end and the loop terminates. That is the whole algorithm: meeting means a cycle, reaching null means none.
The implementation detail that matters is the loop guard. Check both fast and fast.next before advancing two nodes, since stepping twice from the last node dereferences null. Checking only fast crashes on every acyclic list of even length.
Another small trap is starting both pointers at the head and testing equality before moving — they are trivially equal at the start, so every list reports a cycle. Advance first, then compare.
Finding where the cycle begins is Linked List Cycle II, which restarts one pointer at the head after the meeting.
Floyd's tortoise and hare. If a cycle exists the fast pointer laps the slow one and they must meet; if not, fast simply falls off the end. The reason they can't skip past each other is that the gap shrinks by exactly one each step — that argument is what makes O(1) space possible where a hash set would need O(n).
Approach
Before reading on: price up what counting everything costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Start with the hash set version
Store each visited node and report a cycle when one reappears. Correct and simple at O(n) time and O(n) space — the constant-space version is an improvement on space alone.
Move two pointers at different speeds
Advance slow one node and fast two per iteration. Once both are inside a loop, the fast pointer gains exactly one position per step.
See why they must meet
The gap shrinks by one each iteration and cannot skip past zero, so it hits zero exactly. A meeting is guaranteed, not probabilistic — that is why the algorithm is correct rather than merely likely to work.
Guard both null checks
Test both fast and fast.next before advancing two nodes. Checking only fast dereferences null on every acyclic list of even length.
Advance before comparing
Both pointers start at the head, so testing equality first reports a cycle on every list. Move, then compare.
Return on the terminating condition
Meeting means a cycle exists; the fast pointer reaching null means it does not. Nothing further is needed for this problem.
Cost of Floyd's algorithm
The slow pointer travels at most the list length plus the cycle length, giving O(n) time and O(1) space — the space win over the hash set. Locating the cycle's start is Linked List Cycle II.
Solution & live demo
Common pitfalls
Comparing values instead of identity
if slow.val == fast.val: return True
if slow is fast: return True
Two distinct nodes can easily hold the same value in a perfectly acyclic list, producing a false positive. A cycle means the pointers reach the same node, which is an identity question.
Advancing both by one
slow = slow.next fast = fast.next
slow = slow.next fast = fast.next.next
Equal speeds keep the gap constant forever, so they never meet inside a cycle and the loop runs indefinitely. The difference in speed is the entire mechanism.
Checking for a meeting before moving
while fast and fast.next:
if slow is fast: return True
slow = slow.next
fast = fast.next.next slow = slow.next
fast = fast.next.next
if slow is fast: return TrueBoth start at head, so testing before the first move reports a cycle on every non-empty list. The comparison belongs after the advance.
Edge cases
fast or fast.next becomes null and the loop exits with false.
The pointers still meet inside the loop; identity (is) compares nodes, not values.
The loop condition is false immediately, returning false.