Part 2 · Problems · Linked list
Linked List Cycle
#141 · Easy · LeetCode
Does the linked list loop back on itself?
3->2->0->-4->(back to 2) -> true
Ask before coding
- O(1) memory expected?
Hint
A slow runner and a fast runner on a circular track meet.
Approach
slow moves 1, fast moves 2. If fast hits the end, no cycle. If they meet, there's a cycle.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function hasCycle(head) {
let slow = head,
fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Traps
- Check fast && fast.next before fast.next.next.
- A Set of visited nodes works too, with O(n) memory.
Say out loud: A visited set is easy. Floyd's two pointers do it with O(1) memory.