Find length of Loop | Complete Guide with 2 Different Solutions

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.

Here’s the [Problem Link] to begin with.

Note: ‘c‘ is the position of the node which is the next pointer of the last node of the linkedlist. If c is 0, then there is no loop.

Examples:

Input: head: 1 → 2 → 3 → 4 → 5, c = 2
Output: 4
Explanation: There exists a loop in the linked list and the length of the loop is 4.

Input: head: 25 → 14 → 19 → 33 → 10 → 21 → 39 → 90 → 58 → 45, c = 4
Output: 7
Explanation: The loop is from 33 to 45. So length of loop is 33 → 10 → 21 → 39 → 90 → 58 → 45 = 7.
The number 33 is connected to the last node of the linkedlist to form the loop because according to the input the 4th node from the beginning(1 based indexing) 
will be connected to the last node in the LinkedList.

Input: head: 0 → 1 → 2 → 3, c = 0
Output: 0
Explanation: There is no loop.

Constraints:
1 ≤ no. of nodes ≤ 10⁶
0 ≤ node.data ≤ 10⁶
0 ≤ c ≤ n-1

Solution 1: Brute Force Approach (Using Dictionary)

Intuition

Think of this like taking a walk and marking each step with a number. If you ever come back to a place you’ve been before, you can easily calculate how many steps you took in the loop by subtracting your current step number from the step number when you first visited that place!

Detailed Approach

1. Create a Position Tracker: Use a dictionary to store each node and the position where we first encountered it
2. Walk and Record: Move through the list, recording each node’s position
3. Check for Revisit: At each node, check if we’ve seen it before
4. Calculate Loop Length: If we find a repeated node, subtract its first position from current position
5. No Loop Found: If we reach the end, return 0

Code

class Solution:
    def countNodesInLoop(self, head):
        my_dict = dict()     # Dictionary to store node -> position mapping
        temp = head          # Current node we're examining
        travel = 0           # Current position counter
        
        while temp is not None:
            if temp in my_dict:           # Check if we've seen this node before
                return travel - my_dict[temp]  # Calculate loop length
            my_dict[temp] = travel        # Record current node's position
            travel += 1                   # Increment position counter
            temp = temp.next              # Move to next node
        
        return 0                         # No loop found

Code Explanation

We use a dictionary to map each node to its position in our traversal. As we walk through the list, we check if the current node already exists in our dictionary. If it does, we’ve found the start of the loop! The length of the loop is simply the difference between our current position and the position where we first saw this node. If we reach the end of the list without finding any repeated nodes, there’s no loop.

Dry Run

Let’s trace through: 1 -> 2 -> 3 -> 4 -> 2 (4 points back to 2)

Step 1: temp=1, travel=0, my_dict={}, add 1: my_dict={1: 0}
Step 2: temp=2, travel=1, my_dict={1: 0}, add 2: my_dict={1: 0, 2: 1}
Step 3: temp=3, travel=2, my_dict={1: 0, 2: 1}, add 3: my_dict={1: 0, 2: 1, 3: 2}
Step 4: temp=4, travel=3, my_dict={1: 0, 2: 1, 3: 2}, add 4: my_dict={1: 0, 2: 1, 3: 2, 4: 3}
Step 5: temp=2, travel=4, my_dict={1: 0, 2: 1, 3: 2, 4: 3}, 2 found!

• Loop length = 4 – 1 = 3

Result: Loop length is 3!

Time and Space Complexity

• Time Complexity: O(n) – We visit each node at most once before detecting the loop
• Space Complexity: O(n) – We store all nodes in the dictionary

Simplifying It

This approach is like keeping a detailed travel log. When you revisit a place, you can easily count how many steps you took in the circular path by looking at your log. Simple but uses extra memory to store all the positions.

Solution 2: Optimal Approach (Floyd’s Algorithm + Loop Counting)

Intuition

This is a two-step process! First, we use the “tortoise and hare” technique to detect if there’s a loop. Once we find the loop, we keep one pointer fixed and move the other pointer around the loop, counting steps until they meet again. It’s like sending someone around a circular track and counting how many steps they take to complete one full lap!

Detailed Approach

1. Phase 1 – Detect Loop: Use two pointers (slow and fast) to detect if a cycle exists
2. Phase 2 – Count Loop Length: Once loop is detected, keep one pointer fixed
3. Count Steps: Move the other pointer around the loop, counting each step
4. Complete the Circle: When both pointers meet again, we’ve counted the entire loop

Code

class Solution:
    def countNodesInLoop(self, head):
        slow = head          # Slow pointer (tortoise)
        fast = head          # Fast pointer (hare)
        
        # Phase 1: Detect if loop exists
        while fast and fast.next:
            slow = slow.next      # Move slow pointer 1 step
            fast = fast.next.next # Move fast pointer 2 steps
            
            if slow == fast:      # Loop detected!
                # Phase 2: Count loop length
                slow = slow.next  # Move slow one step ahead
                count = 1         # Start counting from 1
                
                while slow is not fast:  # Count until they meet again
                    count += 1           # Increment counter
                    slow = slow.next     # Move slow pointer
                
                return count      # Return loop length
        
        return 0                 # No loop found

Code Explanation

This solution works in two phases. In Phase 1, we use the classic two-pointer technique to detect if a loop exists. When both pointers meet, we know there’s a loop. In Phase 2, we move one pointer one step ahead and start counting. We keep moving this pointer around the loop until it meets the other pointer again. The count gives us the exact length of the loop.

Dry Run

Let’s trace through: 1 -> 2 -> 3 -> 4 -> 2 (4 points back to 2)

Phase 1 – Loop Detection:

• Initial: slow=1, fast=1
• Step 1: slow=2, fast=3
• Step 2: slow=3, fast=2 (in loop)
• Step 3: slow=4, fast=4
• Loop detected! slow == fast at node 4

Phase 2 – Count Loop Length:

• Move slow one step: slow=2, fast=4, count=1
• Step 1: slow=3, fast=4, count=2
• Step 2: slow=4, fast=4, slow == fast, return count=2

Wait, let me recalculate this more carefully…

Actually, let me trace this again:

• When slow and fast meet in the loop, let’s say they meet at some node
• We move slow one step ahead and start counting
• We keep moving slow until it comes back to the meeting point
• The count will be the length of the loop

Result: Loop length is 3 (nodes 2, 3, 4)

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list to detect the loop, then traverse the loop once to count
• Space Complexity: O(1) – We only use two pointer variables and a counter

Simplifying It

This is like having two people on a circular track. First, we confirm they’re on a circular track by having them run at different speeds until they meet. Then, we keep one person fixed and have the other person walk around the track once, counting their steps. When they meet again, we know the track’s length!

Summary

The two pointers approach is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you’re first learning about loop detection.

Both solutions effectively solve the problem, but the optimal solution demonstrates the power of Floyd’s cycle detection algorithm,

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.not just for finding cycles, but for measuring them too!