Problem overview
The method hasCycle receives head, a pointer to the first ListNode of a singly linked list. It returns true if following the next pointers from head can lead back to a node that was already visited, which means the list contains a cycle. It returns false if the list ends, that is, if some node has next == NULL.
The statement mentions a number pos, the index of the node that the tail connects back to. It only describes how the tests build their lists. The method never receives it, so it has to detect the cycle from the nodes alone. The list can also be empty (head is null), because the number of nodes is allowed to be 0.
In the first example the list is 3 → 2 → 0 → -4, and the last node points back to the node holding 2, so the answer is true. In the third example there is a single node whose next is null, so the answer is false.
Approach: two pointers at different speeds
The direct idea is to remember every node you visit. Walk along the list, store each node's address in an unordered_set<ListNode*>, and report a cycle if you ever meet an address that is already in the set:
bool hasCycleWithSet(ListNode* head) {
unordered_set<ListNode*> seen;
for (ListNode* node = head; node != nullptr; node = node->next) {
if (!seen.insert(node).second) {
return true;
}
}
return false;
}
This is correct and runs in O(n) time, but it uses O(n) extra memory. The statement's follow-up asks for constant memory, and the lesson solves it with Floyd's tortoise and hare algorithm.
The algorithm uses two pointers that both start at head. The pointer slow moves one node per step and fast moves two nodes per step.
- If the list has no cycle,
fastreaches the end first. The loop stops and the answer isfalse. - If the list has a cycle, both pointers eventually run around it.
fastkeeps catching up withslow, and at some point they point to the same node. The answer istrue.
Why the pointers must meet
Once both pointers are inside the cycle, look at the distance from fast forward around the loop to slow. In every step fast advances two nodes and slow advances one, so that distance shrinks by exactly one. A distance that goes down one at a time cannot jump over zero, so it reaches zero, and zero means both pointers are on the same node. Because the gap changes by one, fast cannot step over slow without landing on it. With a larger speed difference, such as three nodes against one, the gap would shrink by two at a time and could jump over zero.
A worked example
Take the list 3 → 2 → 0 → -4 with the tail pointing back to the node holding 2. Both pointers start at the node holding 3.
| Step | slow is at | fast is at | Same node? |
|---|---|---|---|
| 1 | 2 | 0 | no |
| 2 | 0 | 2 | no |
| 3 | -4 | -4 | yes, return true |
Step by step
- Declare
slowandfastasListNode*and set both tohead. - Loop while
fast != NULL && fast->next != NULL.fastjumps two nodes, so it needs two nodes ahead of it. Iffastorfast->nextis null, the list ends and there is no cycle. - Move
slowone node withslow = slow->next. - Move
fasttwo nodes withfast = fast->next->next. This is safe, because the loop condition just proved thatfast->nextis not null. - Compare after moving. If
slow == fast, returntrue. When the loop finishes without a meeting, returnfalse.
The solution in C++
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
The C++ details behind these lines:
- The order of the two conditions matters. The operator
&&stops at the first false operand. Iffastis null,fast->nextis never evaluated. Swapping the two conditions would dereference a null pointer on lists with an even number of nodes and no cycle, which is undefined behaviour. slow == fastcompares addresses. It asks whether both pointers point to the same node, not whether the nodes hold equal values. A list such as1 → 1 → 1has equal values and no cycle.NULLandnullptr. The starter code's constructors usenullptr, and this solution tests againstNULL. For pointers the two comparisons behave the same here. In new code,nullptris the preferred spelling.- The method does not modify the list and allocates nothing.
Complexity
Time: O(n). Without a cycle, fast reaches the end after about n / 2 iterations. With a cycle, slow needs at most n steps to get into the cycle, and after that the distance between the pointers closes by one per iteration, which is at most the cycle length. Together this is at most about n iterations.
Space: O(1). The method keeps two pointers, however long the list is. This is the improvement over the set-based version.
Edge cases and common mistakes
- Empty list. With
head == NULLthe loop condition is false at once and the method returnsfalse. - One node. If its
nextis null, the loop does not run and the answer isfalse. If itsnextpoints to itself, then one step laterslowandfastare both that node, and the answer istrue. - Comparing before moving. Both pointers start at
head, so a check placed before the moves would always returntrue. The comparison belongs after the moves. - Checking only
fast != NULL. The expressionfast->next->nextwould then dereference null wheneverfaststands on the last node. - Comparing values. Duplicated values do not mean a cycle. Compare the pointers.
Testing
[3, 2, 0, -4]with the tail joined to index 1 givestrue.[1, 2]with the tail joined to index 0 givestrue.[1]with no cycle givesfalse.[](a nullhead) givesfalse.[1, 2, 3, 4, 5]with no cycle givesfalse, and with the tail joined to index 4 (the last node points to itself) givestrue.
The same two pointers solve a related task: when fast reaches the end of a list without a cycle, slow stands on the middle node. For an even number of nodes, it is the second of the two middle ones.
