Floyd Cycle Detection
A cycle in a linked list occurs when a node's next points back to a previous node, creating an infinite loop. Floyd's Cycle Detection Algorithm (tortoise and hare) detects cycles in O(n) time and O(1) space.
The idea: use two pointers – slow (moves one step at a time) and fast (moves two steps). If they meet, there is a cycle. If fast reaches null, no cycle.
Detect Cycle
public boolean hasCycle() {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
Find Start of Cycle
After detection, reset one pointer to head and move both one step at a time; they meet at cycle start.
public Node detectCycleStart() {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
Two Minute Drill
- Floyd's cycle detection uses slow and fast pointers.
- If pointers meet, cycle exists; if fast reaches null, no cycle.
- To find cycle start, reset one pointer to head and move both one step; they meet at start.
- Space O(1), time O(n).
Need more clarification?
Drop us an email at career@quipoinfotech.com