ASAPUtils
Optimal solution
bool hasCycle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
function hasCycle(head) {
let slow = head, fast = head;
while (fast?.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
Proof
Without a cycle, fast follows the finite chain to null. With a cycle, both pointers eventually enter it. From then on, fast moves one extra cycle position per iteration relative to slow, so it must lap slow and occupy the same node.
Complexity
Both pointers take O(n) total moves before termination or meeting. Only two references are stored: O(1) space. A visited set is simpler but uses O(n) space.
Traps
- Dereferencing
fast.next.nextwithout checkingfastandfast.next. - Checking
slow === fastbefore moving; they start equal. - Comparing values rather than node identity.
- Assuming the meeting node is the cycle entrance; that is a separate second phase.
Blank re-solve prompt
Explain the lapping proof in one sentence, then write the exact null guard from memory. Test empty, one-node-null, one-node-self-cycle, and a longer cycle.