> For the complete documentation index, see [llms.txt](https://hunterdii.gitbook.io/gfg-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hunterdii.gitbook.io/gfg-solution/september-2025-gfg-solution/06-sep-find-length-of-loop.md).
# 06. Find Length of Loop
The problem can be found at the following link: π [Question Link](https://www.geeksforgeeks.org/problems/find-length-of-loop/1)
## **𧩠Problem Description**
Given the head of a linked list, determine whether the list contains a loop. If a loop is present, return the **number of nodes in the loop**, otherwise return **0**.
**Note:** Internally, pos(1 based index) is used to denote the position of the node that tail's next pointer is connected to. If pos = 0, it means the last node points to null, indicating there is no loop. Note that pos is not passed as a parameter.
## **π Examples**
### Example 1
```cpp
Input: pos = 2
Output: 4
Explanation: There exists a loop in the linked list and the length of the loop is 4.
```
### Example 2
```cpp
Input: pos = 3
Output: 3
Explanation: The loop is from 19 to 10. So length of loop is 19 β 33 β 10 = 3.
```
### Example 3
```cpp
Input: pos = 0
Output: 0
Explanation: There is no loop.
```
## **π Constraints**
* $1 \le \text{number of nodes} \le 10^5$
* $1 \le \text{node->data} \le 10^4$
* $0 \le \text{pos} < \text{number of nodes}$
## **β
My Approach**
The optimal approach uses **Floyd's Cycle Detection Algorithm** (also known as the **Tortoise and Hare Algorithm**):
### **Floyd's Cycle Detection + Loop Length Calculation**
1. **Phase 1 - Loop Detection:**
* Use two pointers: `slow` (moves 1 step) and `fast` (moves 2 steps).
* If there's a loop, `slow` and `fast` will eventually meet inside the loop.
* If `fast` reaches NULL, there's no loop.
2. **Phase 2 - Loop Length Calculation:**
* Once loop is detected (when `slow == fast`), keep one pointer fixed.
* Move the other pointer one step at a time until it completes one full cycle.
* Count the steps taken - this gives the loop length.
3. **Edge Cases:**
* If no loop exists, return 0.
* Handle single node and empty list cases.
## π Time and Auxiliary Space Complexity
* **Expected Time Complexity:** O(n), where n is the number of nodes in the linked list. In the worst case, we traverse the entire list once to detect the loop, and then traverse the loop once more to count its length.
* **Expected Auxiliary Space Complexity:** O(1), as we only use a constant amount of additional space for the two pointers, regardless of the size of the linked list.
## **π§βπ» Code (C++)**
```cpp
class Solution {
public:
int lengthOfLoop(Node* head) {
Node *s = head, *f = head;
while (f && f->next) {
s = s->next;
f = f->next->next;
if (s == f) {
int cnt = 1;
while (s->next != f) s = s->next, cnt++;
return cnt;
}
}
return 0;
}
};
```
β‘ View Alternative Approaches with Code and Analysis
### π **2οΈβ£ Hash Set Approach**
#### π‘ Algorithm Steps:
1. Traverse the linked list and store each node address in a hash set.
2. When we encounter a node that's already in the set, we've found the loop start.
3. Continue traversal from loop start, counting nodes until we return to the same node.
4. Return the count of nodes in the loop.
```cpp
class Solution {
public:
int lengthOfLoop(Node* head) {
unordered_set visited;
Node* curr = head;
while (curr) {
if (visited.count(curr)) {
int len = 1;
Node* start = curr->next;
while (start != curr) start = start->next, len++;
return len;
}
visited.insert(curr);
curr = curr->next;
}
return 0;
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Single traversal with hash operations
* **Auxiliary Space:** πΎ O(n) - Hash set to store visited nodes
#### β
**Why This Approach?**
* Straightforward logic with clear loop detection
* No complex pointer manipulation required
* Easy to debug and understand
### π **3οΈβ£ Modified Floyd's with Distance Calculation**
#### π‘ Algorithm Steps:
1. Use Floyd's algorithm to detect if a loop exists.
2. Once loop is detected, keep slow pointer at meeting point.
3. Move fast pointer to head and advance both pointers one step at a time.
4. When they meet again, that's the loop start, then count the loop length.
```cpp
class Solution {
public:
int lengthOfLoop(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return 0;
fast = head;
while (slow != fast) slow = slow->next, fast = fast->next;
int length = 1;
fast = slow->next;
while (fast != slow) fast = fast->next, length++;
return length;
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Multiple passes but still linear
* **Auxiliary Space:** πΎ O(1) - Only pointer variables used
#### β
**Why This Approach?**
* Finds exact loop start position
* Constant space complexity
* Classical two-phase Floyd's cycle detection
### π **4οΈβ£ Single Pass Optimized Floyd's**
#### π‘ Algorithm Steps:
1. Run standard Floyd's cycle detection algorithm.
2. As soon as slow and fast pointers meet, start counting from that position.
3. Move one pointer step by step until it completes one full loop cycle.
4. Return the count without needing separate loop start detection.
```cpp
class Solution {
public:
int lengthOfLoop(Node* head) {
if (!head || !head->next) return 0;
Node *slow = head->next, *fast = head->next->next;
while (fast && fast->next && slow != fast) {
slow = slow->next;
fast = fast->next->next;
}
if (!fast || !fast->next) return 0;
int count = 1;
fast = slow->next;
while (fast != slow) {
fast = fast->next;
count++;
}
return count;
}
};
```
#### π **Complexity Analysis:**
* **Time:** β±οΈ O(n) - Optimized single detection phase
* **Auxiliary Space:** πΎ O(1) - Minimal pointer usage
#### β
**Why This Approach?**
* Most optimized runtime performance
* Minimal pointer operations
* Direct loop length calculation
### π **π Comparison of Approaches**
| π **Approach** | β±οΈ **Time Complexity** | πΎ **Space Complexity** | β
**Pros** | β οΈ **Cons** |
| -------------------------- | ---------------------- | ----------------------- | -------------------- | -------------------------------- |
| π·οΈ **Direct Floyd's** | π’ O(n) | π’ O(1) | π Fastest execution | π§ Requires loop detection first |
| π **Hash Set** | π’ O(n) | π‘ O(n) | π Clearest logic | πΎ Extra memory overhead |
| π **Modified Floyd's** | π’ O(n) | π’ O(1) | π― Finds loop start | π Multiple traversal phases |
| π **Single Pass Floyd's** | π’ O(n) | π’ O(1) | β Most optimized | π§ Slightly complex logic |
#### π **Best Choice Recommendation**
| π― **Scenario** | ποΈ **Recommended Approach** | π₯ **Performance Rating** |
| --------------------------------- | ---------------------------- | ------------------------- |
| π
**Maximum performance needed** | π₯ **Direct Floyd's** | β
β
β
β
β
|
| π **Code clarity priority** | π₯ **Hash Set** | β
β
β
β
β |
| π§ **Need loop start position** | π₯ **Modified Floyd's** | β
β
β
β
β |
| π― **Competitive programming** | π
**Single Pass Floyd's** | β
β
β
β
β
|
## **β Code (Java)**
```java
class Solution {
public int lengthOfLoop(Node head) {
Node s = head, f = head;
while (f != null && f.next != null) {
s = s.next;
f = f.next.next;
if (s == f) {
int cnt = 1;
while (s.next != f) {
s = s.next;
cnt++;
}
return cnt;
}
}
return 0;
}
}
```
## **π Code (Python)**
```python
class Solution:
def lengthOfLoop(self, head):
s, f = head, head
while f and f.next:
s, f = s.next, f.next.next
if s == f:
cnt = 1
while s.next != f:
s, cnt = s.next, cnt + 1
return cnt
return 0
```
## π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [π¬ Any Questions?](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let's make this learning journey more collaborative!
β **If you find this helpful, please give this repository a star!** β
***
#### πVisitor Count
