Beginner LevelData Structures & Algorithms
How do you detect a cycle in a Linked List (Floyd's Algorithm)?
ā Interview Prompt: Detect a cycle in a singly linked list using Floyd's Tortoise and Hare algorithm in O(N) time and O(1) space.
Floyd's Cycle Detection (Tortoise and Hare) uses two pointers:
ā¢
Slow pointer: Moves 1 step at a time.
ā¢
Fast pointer: Moves 2 steps at a time.
If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle.
ā¢
Time: $O(N)$, Space: $O(1)$.
Finding Cycle Entry Point:
After detection, reset one pointer to the head and advance both one step at a time. They meet at the cycle's entry node.
Code Implementation Example
typescript
function hasCycle(head: ListNode | null): boolean {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true; // cycle detected!
}
return false;
}
// Find cycle entry node
function detectCycleStart(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
slow = head; // reset to head
while (slow !== fast) { slow = slow!.next; fast = fast!.next; }
return slow; // cycle entry
}
}
return null;
}š”Floyd's Tortoise and Hare cycle detection in O(N) time, O(1) space.
šÆ Interview Key Takeaway
Floyd's algorithm detects cycles in O(N) / O(1) without extra memory. A hashtable approach would use O(N) space.
#DSA#Linked List#Cycle Detection#Floyd's Algorithm#Beginner
Back to all Data Structures & Algorithms Questionsā