Q7: Linked List Cycle Detection (Floyd's Tortoise and Hare)
Detect whether a linked list contains a cycle using two pointers moving at different speeds (slow moves 1 step, fast moves 2 steps).
Floyd's Cycle Finding Algorithm
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}💡 Slow moves one node at a time while fast moves two nodes. If there is no cycle, fast reaches null. If a cycle exists, fast meets slow inside the loop.
Key Takeaways
- Floyd's algorithm detects cycles in O(n) time and O(1) space.
- If a cycle exists, the fast pointer eventually catches up and equals the slow pointer.
Knowledge Check
What happens if Floyd's cycle detection is run on a linear list with no cycle?