L15: Find the Length of a Loop in a Linked List

Finding the length of a loop in a linked list is a classic algorithmic problem that builds directly upon cycle detection techniques. Given the head of a linked list, our goal is to determine if a cycle exists; if it does, we must return the exact number of nodes that make up the loop. If the linked list is linear and terminates at null, we return 0.

1. Problem Statement and Definition of a Loop

A loop exists in a linked list if traversal can continue indefinitely without hitting a null reference because a node's next pointer directs back to a previously visited node.

• Loop Length Definition: The count of unique nodes that form the cycle path. Starting from any node within the loop, traversing the next pointers until you return to the starting node yields the exact length of the loop.
• Linear Linked List: If no cycle exists, the traversal terminates safely at null, meaning the loop length is 0.

2. Approach 1: The Brute Force Hashing Technique

The most intuitive way to remember whether we have visited a node before is by using a hash map. Because a loop forces us to revisit nodes, tracking visitation history allows us to compute the loop's length on the fly.

Mental Model & Timer Analogy

Imagine walking through a maze where every step takes 1 second (acting as a timer). If you record the exact second (timestamp) you enter each room, the moment you step into a room you have already visited, you can determine how long the loop took by subtracting the past timestamp from your current timer.

Algorithm Steps

1. Initialize a hash map to store (Node, Timer) pairs.
2. Initialize a traversal pointer (temp) at the head and a timer integer at 1.
3. Traverse the linked list node by node:
   • Check if the current node already exists in the hash map.
   • If Yes (Loop Found): The length of the loop is Current Timer - Stored Timer of that Node. Return this value immediately.
   • If No: Store (temp, timer) in the hash map, increment the timer, and advance temp = temp.next.
4. If traversal reaches null, the list is linear; return 0.

Pseudocode for Hashing Approach

public int findLengthUsingMap(Node head) {
    HashMap<Node, Integer> visitedNodes = new HashMap<>();
    Node temp = head;
    int timer = 1;
    
    while (temp != null) {
        if (visitedNodes.containsKey(temp)) {
            int previousTimer = visitedNodes.get(temp);
            return timer - previousTimer; // Loop length calculation
        }
        visitedNodes.put(temp, timer);
        timer++;
        temp = temp.next;
    }
    
    return 0; // Linear linked list, no loop
}

3. Complexity Analysis of the Hashing Approach

While the hashing technique is simple to implement and understand, it comes with memory trade-offs:

Because an $O(N)$ auxiliary space complexity is suboptimal for memory-constrained environments, interviewers will typically ask for an optimized $O(1)$ space solution.

4. Approach 2: Optimal Tortoise and Hare Algorithm

To achieve $O(1)$ space complexity, we eliminate the hash map entirely and use two pointers: a Slow pointer (tortoise) moving 1 step at a time, and a Fast pointer (hare) moving 2 steps at a time.

How the Collision Occurs

1. Both slow and fast pointers start at the head.
2. slow moves forward by 1 node: slow = slow.next.
3. fast moves forward by 2 nodes: fast = fast.next.next.
4. If there is a loop, fast will eventually loop around and meet slow at some intersection node.
5. If fast or fast.next reaches null, the list is linear, meaning no loop exists.

5. Step-by-Step Flow: Calculating Loop Length After Collision

Once slow and fast collide inside the loop, we know a cycle exists. To find its length:

1. Fix one pointer (e.g., keep fast or slow stationary at the collision point).
2. Initialize a counter variable to 1.
3. Move the other pointer (or a temporary reference) step-by-step using pointer = pointer.next.
4. Increment the counter on each step until it loops all the way around and points back to the stationary collision node.
5. The final value of counter is the exact length of the loop.

6. Complete Production-Ready Code Implementations

Below are the complete, tested implementations in C++ and Java incorporating cycle detection and length calculation.

C++ Implementation

#include <iostream>

using namespace std;

// Definition for singly-linked list node.
class Node {
public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = nullptr;
    }
};

class Solution {
private:
    int countLoopLength(Node* slow, Node* fast) {
        int count = 1;
        fast = fast->next;
        while (slow != fast) {
            count++;
            fast = fast->next;
        }
        return count;
    }

public:
    int lengthOfLoop(Node* head) {
        Node* slow = head;
        Node* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            // Collision detected
            if (slow == fast) {
                return countLoopLength(slow, fast);
            }
        }
        
        return 0; // Linear list, no loop
    }
};

Java Implementation

// Definition for singly-linked list node.
class Node {
    int data;
    Node next;
    Node(int val) {
        data = val;
        next = null;
    }
}

class Solution {
    private int countLoopLength(Node slow, Node fast) {
        int count = 1;
        fast = fast.next;
        while (slow != fast) {
            count++;
            fast = fast.next;
        }
        return count;
    }

    public int lengthOfLoop(Node head) {
        Node slow = head;
        Node fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            // Collision detected
            if (slow == fast) {
                return countLoopLength(slow, fast);
            }
        }
        
        return 0; // Linear list, no loop
    }
}

7. Summary and Key Takeaways

• Problem Core: Finding the loop length requires first detecting that a cycle exists and then measuring the distance of one complete revolution around the cycle.
• Brute Force Strategy: Use a hash map to store (Node, Timestamp) pairs; subtracting the initial timestamp from the revisiting timestamp yields the loop length in $O(N)$ time and $O(N)$ space.
• Optimal Strategy: Apply the Tortoise and Hare Algorithm (slow and fast pointers) to detect the loop in $O(N)$ time and $O(1)$ space.
• Length Extraction: Upon pointer collision, hold one pointer steady, traverse the loop until you return to it, and count each step.
• Linear List Safety: Always guard against null references (fast != null && fast.next != null) to ensure graceful handling of non-looped linked lists, returning 0 when no cycle is found.