Detect a loop in a linked list
💡 Concept: Loop Detection in Linked List
Detecting a loop involves checking if a linked list contains a cycle where a node points back to a previous node.
📘 Quick Intro
Floyd’s cycle-finding algorithm (tortoise and hare) is a common approach.
🧠 Analogy
Like two runners on a track, one faster than the other, meeting if the track loops.
🔧 Technical Explanation
- Use two pointers moving at different speeds.
- If pointers meet, a loop exists.
- If pointers reach null, no loop.
- Algorithm has O(n) time complexity.
- Requires no extra memory.
🎯 Use Cases
- ✅ Detect cycles in data structures.
- ✅ Debugging linked list issues.
- ✅ Prevent infinite loops.
- ✅ Algorithm interviews.
💻 Code Example
public class Node {
public int Data;
public Node Next;
}
public bool HasLoop(Node head) {
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;
}
❓ Interview Q&A
Q1: What is Floyd’s cycle-finding algorithm?
A: A two-pointer technique to detect cycles.
Q2: Can this detect all loops?
A: Yes, any cycle in linked list.
Q3: Time complexity?
A: O(n).
Q4: Does it use extra memory?
A: No.
Q5: What if list is empty?
A: Returns false.
Q6: Can you find loop start?
A: Yes, with extra steps.
Q7: Is it thread-safe?
A: Depends on usage.
Q8: Alternatives?
A: Using hash sets.
Q9: Can it be used for doubly linked list?
A: Yes.
Q10: Is it optimal?
A: Yes, in time and space.
📝 MCQs
Q1. What is Floyd’s cycle-finding algorithm?
- Stack
- Queue
- Two-pointer technique
- Recursion
Q2. Can this detect all loops?
- No
- Sometimes
- Yes
- Rarely
Q3. Time complexity?
- O(1)
- O(n)
- O(n^2)
- O(log n)
Q4. Does it use extra memory?
- Yes
- No
- Maybe
- Sometimes
Q5. What if list is empty?
- Throws error
- Returns false
- Returns true
- Infinite loop
Q6. Can you find loop start?
- No
- Yes
- Sometimes
- Never
Q7. Is it thread-safe?
- Always
- Never
- Depends
- Rarely
Q8. Alternatives?
- Arrays
- Hash sets
- Lists
- Stacks
Q9. Can it be used for doubly linked list?
- No
- Yes
- Maybe
- Rarely
Q10. Is it optimal?
- No
- Yes
- Sometimes
- Rarely
💡 Bonus Insight
Floyd’s algorithm is elegant, using two pointers to detect cycles efficiently without extra memory.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!