Q9: How do you detect a cycle in a LinkedList using Floyd's Cycle-Finding Algorithm?
Use Floyd's Tortoise and Hare Algorithm. Initialize two pointers: slow and fast at head. Move slow by 1 step and fast by 2 steps. If a cycle exists, fast and slow will eventually meet at the same node. If fast reaches null, no cycle exists.
Floyd's Cycle Detection
public class LinkedListCycle {
public static boolean hasCycle(ListNode head) {
if (head == null) return false;
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;
}
}💡 If the fast pointer laps the slow pointer, a cycle exists in the list.
Key Takeaways
- Two pointers moving at different speeds ($1 imes$ vs $2 imes$).
- Detects cycles in $O(n)$ time using $O(1)$ memory.
Knowledge Check
Why is Floyd's Cycle detection algorithm preferred over storing visited nodes in a HashSet?