🔗 Try This Problem
Practice here:
https://practice.geeksforgeeks.org/problems/find-length-of-loop/1
📌 Problem Overview
You are given the head of a singly linked list.
Your task is:
- Detect whether a loop (cycle) exists
- If a loop exists → return the length of the loop
- If no loop exists → return 0
🧠 Understanding the Problem
A loop in a linked list means:
👉 A node’s next pointer is pointing to a previous node, forming a cycle.
Example
1 → 2 → 3 → 4 → 5
↑ ↓
← ← ← ←
Here:
- Loop starts at node
3 - Loop nodes =
3 → 4 → 5 - Loop length = 3
💡 Intuition — How to Think About This Problem
There are two main challenges:
🔹 1. Detect if a loop exists
🔹 2. Find the length of that loop
🤔 Brute Force Thinking
- Store visited nodes in a HashSet
- If node repeats → loop detected
✔ Works
❌ Extra space O(n)
🚀 Optimized Thinking (Floyd’s Cycle Detection)
We use:
- Slow pointer → moves 1 step
- Fast pointer → moves 2 steps
🧠 Key Idea
👉 If a loop exists:
- Fast pointer will eventually meet slow pointer
👉 If no loop:
- Fast pointer reaches
null
🎥 Visual Intuition & Dry Run
⚙️ Optimized Approach (Step-by-Step)
Step 1: Detect Loop
- Initialize:
slow = head
fast = head
- Move:
slow → 1 step
fast → 2 steps
- If:
slow == fast → loop exists
Step 2: Find Length of Loop
Once loop is detected:
- Keep one pointer fixed
- Move another pointer until it comes back
- Count steps
Why This Works?
Because:
- Inside a loop, traversal becomes circular
- So eventually, we will return to the same node
🧪 Dry Run (Manual Understanding)
Example:
Loop: 3 → 4 → 5 → 3
Step 1: Detect Loop
- Slow and fast meet inside loop
Step 2: Count Loop Length
Start from meeting point:
Move one pointer:
3 → 4 → 5 → 3
Count = 3
💻 Code (Java)
class Solution {
public int lengthOfLoop(Node head) {
Node slow = head;
Node fast = head;
// Step 1: Detect loop
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
// Step 2: Count loop length
int length = 1;
Node temp = slow.next;
while(temp != slow){
temp = temp.next;
length++;
}
return length;
}
}
return 0; // No loop
}
}
⏱️ Complexity Analysis
| Type | Value |
| Time Complexity | O(n) |
| Space Complexity | O(1) |
🔍 Deep Insight — Why Fast Meets Slow?
- Fast moves twice as fast as slow
- Inside a loop → paths become circular
- Difference in speed guarantees collision
👉 This is a mathematical certainty in cyclic structures
⚠️ Edge Cases
- No loop → return 0
- Single node loop → return 1
- Large loop → still works efficiently
🧩 Key Takeaways
- Floyd’s Cycle Detection is powerful
- Loop detection + loop length can be done in one traversal
- No extra space needed
🏁 Final Thoughts
This problem is a classic linked list concept and very important for interviews.
👉 Once you master this:
- Detect cycle
- Find loop length
- Find loop starting node
All become easier.
