Length of Loop in Linked List

Problem Statement: Given the head of a linked list, determine the length of a loop present in the linked list; if not present, return 0.

Examples

Example 1:

Input Format:

LL: 1  2  3  4  5 

Output: 3
Explanation: A cycle exists in the linked list starting at node 3 -> 4 -> 5 and then back to 3. There are 3 nodes present in this cycle.

Example 2:

Input Format:

LL: 1  2  3  4  9  9

Output: 0

Explanation: In this example, the linked list is linear and does not have a loop hence return 0.

Practice:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach Optimal Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

Brute Force Approach
Algorithm / Intuition

Finding the length of the loop of a linked list is an extension of Detection of Loop so review that article and make sure you are thorough with its approaches.

In recap, a loop in a linked list occurs when there is at least one node that, when used as a starting point, allows us to return to it during traversal.

Approach 1: Brute Force Hashing

While traversing the linked list, employ a timer against each node to keep track of the number of nodes you’ve visited before it. Once a previously visited node is encountered again, the length of the loop can be determined by subtracting the timer values at the two instances of visiting that particular node.

Hence it’s important to keep track of nodes and the timer value associated with them. This can be implemented using a hashmap with nodes as the key and the timer as the value.

Algorithm:

Step 1: Traverse through the LL using the traversal technique of assigning a temp node to the head and iterating by moving to the next element till we reach null. While traversing, keep track of the Visited nodes and the timer value associated in the map data structure.

Step 2: Continue traversing till a node that has already been visited is found. The difference between its timer value in the hashmap and the current timers value will be the length of the linked list.

Step 3: If the traversal is completed, and we reach the last point of the linked list which is null, it means there was no loop, hence we return false.

Code

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Node class represents a
// node in a linked list
class Node {
public:
    // Data stored in the node
    int data;   
    
    // Pointer to the next node in the list
    Node* next;      

    // Constructor with both data and
    // next node as parameters
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as a
    // parameter, sets next to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to return the length 
// of loop using hashing

int lengthOfLoop(Node* head) {
    // Hashmap to store visited
    // nodes and their timer values
    unordered_map<Node*, int> visitedNodes; 
    
    // Initialize pointer to
    // traverse the linked list
    Node* temp = head; 
    
    // Initialize timer to track
    // visited nodes
    int timer = 0; 

    // Traverse the linked list till
    // temp reaches nullptr
    while (temp != NULL) {
        
        // If revisiting a node return
        // the difference of timer values
        if (visitedNodes.find(temp) != visitedNodes.end()) {
            // Calculate the length of the loop
            int loopLength = timer - visitedNodes[temp];
            
            // Return the length of the loop
            return loopLength; 
        }
        // Store the current node and
        // its timer value in the hashmap
        visitedNodes[temp] = timer;
        
        // Move to the next node
        temp = temp->next;
        
         // Increment the timer
        timer++;
    }

    // If traversal is completed and
    // we reach the end of the list (null)
    // means there is no loop
    return 0;
}



int main() {
    // Create a sample linked
    // list with a loop
    
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);
    Node* fifth = new Node(5);

    // Create a loop from
    // fifth to second
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    
    // This creates a loop
    fifth->next = second; 

    int loopLength = lengthOfLoop(head);
    if (loopLength > 0) {
        cout << "Length of the loop: " << loopLength << endl;
    } else {
        cout << "No loop found in the linked list." << endl;
    }

    return 0;
}



import java.util.HashMap;
import java.util.Map;

// Node class represents a node
// in a linked list
class Node {
    // Data stored in the node
    int data;        
    // Pointer to the next node in the list
    Node next;      

    // Constructor with both data
    // and next node as parameters
    Node(int data1, Node next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as
    // a parameter, sets next to null
    Node(int data1) {
        data = data1;
        next = null;
    }
}

public class Main {
    // Function to return the length
    // of loop using hashing
    public static int lengthOfLoop(Node head) {
        // Hashmap to store visited nodes
        // and their timer values
        Map<Node, Integer> visitedNodes = new HashMap<>();
        
        // Initialize pointer to 
        // raverse the linked list
        Node temp = head;
        
        // Initialize timer to
        // track visited nodes
        int timer = 0;

        // Traverse the linked list
        // till temp reaches null
        while (temp != null) {
            // If revisiting a node, return
            // the difference of timer values
            if (visitedNodes.containsKey(temp)) {
                // Calculate the length of the loop
                int loopLength = timer - visitedNodes.get(temp);
                
                // Return the length of the loop
                return loopLength;
            }
            // Store the current node and
            // its timer value in the hashmap
            visitedNodes.put(temp, timer);
            
            // Move to the next node
            temp = temp.next;
            
            // Increment the timer
            timer++;
        }

        // If traversal is completed and we
        // reach the end of the list (null),
        // means there is no loop
        return 0;
    }

    public static void main(String[] args) {
        // Create a linked list with a loop
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);
        Node fifth = new Node(5);

        // Create a loop from fifth to second
        head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        
        // This creates a loop
        fifth.next = second; 

        int loopLength = lengthOfLoop(head);

        if (loopLength > 0) {
            System.out.println("Length of the loop: " + loopLength);
        } else {
            System.out.println("No loop found in the linked list.");
        }
    }
}


class Node:
    def __init__(self, data1, next1=None):
        # Data stored in the node
        self.data = data1
        # Pointer to the next node
        # in the list
        self.next = next1
        
# Function to return the lenght
# of loop when slow and fast are
# on the same node
def find_length(slow, fast):
    
    # count to keep track of 
    # nodes encountered in loop
    cnt = 1
    
    # move fast by one step
    fast = fast.next
    
    # traverse fast till it 
    # reaches back to slow
    while slow != fast:
        
        # at each node increase
        # count by 1 and move fast
        # forward by one step
        
        cnt += 1
        fast = fast.next
    
    # loop terminates when fast reaches
    # slow again and the count is returned
    return cnt
    
# Function to find the length
# of the loop in a linked list
def length_of_loop(head):
    slow = head
    fast = head
    
    # Step 1: Traverse the list to detect a loop
    while fast is not None and fast.next is not None:
        # Move slow one step
        slow = slow.next
        # Move fast two steps
        fast = fast.next.next
        
        # Step 2: If the slow and fast pointers
        # meet, there is a loop
        if slow == fast:
            
            # return the number of nodes
            # in the loop
            return find_length(slow, fast)
    
    return 0


# Create a linked list with a loop
head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(5)

# Create a loop from fifth to second
head.next = second
second.next = third
third.next = fourth
fourth.next = fifth

# This creates a loop
fifth.next = second

loopLength = length_of_loop(head)

if loopLength > 0:
    print("Length of the loop:", loopLength)
else:
    print("No loop found in the linked list.")



function Node(data1, next1) {
    // Data stored in the node
    this.data = data1;
    // Pointer to the next node
    // in the list
    this.next = next1 || null;
}

// Function to return the
// length of loop using hashing
function lengthOfLoop(head) {
    // Hashmap to store visited nodes
    // and their timer values
    var visitedNodes = {};
    
    // Initialize pointer to
    // traverse the linked list
    var temp = head;
    
    // Initialize timer to
    // track visited nodes
    var timer = 0;

    // Traverse the linked list
    // until temp reaches null
    while (temp !== null) {
        // If revisiting a node, return
        // the difference of timer values
        if (visitedNodes.hasOwnProperty(temp)) {
            // Calculate the length of the loop
            var loopLength = timer - visitedNodes[temp];
            
            // Return the length of the loop
            return loopLength;
        }
        // Store the current node and
        // its timer value in the hashmap
        visitedNodes[temp] = timer;
        
        // Move to the next node
        temp = temp.next;
        
        // Increment the timer
        timer++;
    }

    // If traversal is completed and we
    // reach the end of the list (null),
    // it means there is no loop
    return 0;
}

// Create a sample linked list with a loop
var head = new Node(1);
var second = new Node(2);
var third = new Node(3);
var fourth = new Node(4);
var fifth = new Node(5);

// Create a loop from fifth to second
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;

// This creates a loop
fifth.next = second;

var loopLength = lengthOfLoop(head);

if (loopLength > 0) {
    console.log("Length of the loop:", loopLength);
} else {
    console.log("No loop found in the linked list.");
}


Output: Length of the loop: 4

Complexity Analysis

Time Complexity: O(N) The code traverses the entire linked list at least once, where ‘N’ is the number of nodes in the list. Therefore, the time complexity is linear, O(N).

Space Complexity: O(N) The code uses a hashmap/dictionary to store encountered nodes, which can take up to O(N) additional space, where ‘N’ is the number of nodes in the list. Hence, the space complexity is O(N) due to the use of the map to track nodes.

Optimal Approach
Algorithm / Intuition

Approach 2: Tortoise and Hare Algorithm

The previous method uses O(N) additional memory. To enhance efficiency, the Tortoise and Hare Algorithm is introduced as an optimization.

The Tortoise and Hare approach has been discussed in this article

Algorithm

Step 1: Initialise two pointers, `slow` and `fast`, to the head of the linked list. `slow` will advance one step at a time, while `fast` will advance two steps at a time. These pointers will move simultaneously.

Step 2: Traverse the linked list with the `slow` and `fast` pointers. While traversing, repeatedly move `slow` one step and `fast` two steps at a time.

Step 3: Continue this traversal until one of the following conditions is met:

  1. `fast` or `fast.next` reaches the end of the linked list (i.e., becomes null). In this case, there is no loop in the linked list hence it is linear, and the algorithm terminates by returning 0.
  2. `fast` and `slow` pointers meet at the same node. This indicates the presence of a loop in the linked list as we have seen in the detection of loop.

This is the point where the slow and fast have met proving that there is a loop in the linked list. From here onwards we start counting for the length of this loop.

Step 4: Initialise a counter with zero and traverse the linked list using the `fast` pointer again, but this time only move one step at a time while incrementing the counter with each node visited. As the fast pointer reaches back at the slow pointer, the value of the counter will represent the length of the loop.

Code

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Node class represents a
// node in a linked list
class Node {
public:
    // Data stored in the node
    int data;   
    
    // Pointer to the next node in the list
    Node* next;      

    // Constructor with both data and
    // next node as parameters
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as a
    // parameter, sets next to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};

// Function to return the lenght
// of loop when slow and fast are
// on the same node
int findLength(Node* slow, Node* fast){
    
    // count to keep track of 
    // nodes encountered in loop
    int cnt = 1;
    
    // move fast by one step
    fast = fast->next;
    
    // traverse fast till it 
    // reaches back to slow
    while(slow!=fast){
        
        // at each node increase
        // count by 1 and move fast
        // forward by one step
        cnt++;
        fast = fast->next;
    }
    
    // loop terminates when fast reaches
    // slow again and the count is returned
    return cnt;
}
// Function to find the length
// of the loop in a linked list
int lengthOfLoop(Node* head) {
    Node* slow = head;
    Node* fast = head;

    // Step 1: Traverse the list to detect a loop
    while (fast != nullptr && fast->next != nullptr) {
        // Move slow one step
        slow = slow->next;     
        // Move fast two steps
        fast = fast->next->next;

        // Step 2: If the slow and fast pointers
        // meet, there is a loop
        if (slow == fast) {
            // return the number of nodes
            // in the loop
            return findLength(slow, fast);
        }
    }

    // Step 3: If the fast pointer
    // reaches the end, there is no loop
    return 0; 
}


int main() {
    // Create a sample linked
    // list with a loop
    
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);
    Node* fifth = new Node(5);

    // Create a loop from
    // fifth to second
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    
    // This creates a loop
    fifth->next = second; 

    int loopLength = lengthOfLoop(head);
    if (loopLength > 0) {
        cout << "Length of the loop: " << loopLength << endl;
    } else {
        cout << "No loop found in the linked list." << endl;
    }

    return 0;
}


import java.util.HashMap;

// Node class represents a node
// in a linked list
class Node {
    // Data stored in the node
    int data;        
    // Pointer to the next node in the list
    Node next;      

    // Constructor with both data
    // and next node as parameters
    Node(int data1, Node next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as
    // a parameter, sets next to null
    Node(int data1) {
        data = data1;
        next = null;
    }
}

public class LinkedListLoopLength {
    
    // Function to return the lenght
    // of loop when slow and fast are
    // on the same node
    static int findLength(Node slow, Node fast){
        
        // count to keep track of 
        // nodes encountered in loop
        int cnt = 1;
        
        // move fast by one step
        fast = fast.next;
        
        // traverse fast till it 
        // reaches back to slow
        while(slow!=fast){
            
            // at each node increase
            // count by 1 and move fast
            // forward by one step
            cnt++;
            fast = fast.next;
        }
        
        // loop terminates when fast reaches
        // slow again and the count is returned
        return cnt;
    }

    // Function to find the length
    // of the loop in a linked list
    static int lengthOfLoop(Node head) {
        Node slow = head;
        Node fast = head;

        // Step 1: Traverse the list to detect a loop
        while (fast != null && fast.next != null) {
            // Move slow one step
            slow = slow.next;  
            
            // Move fast two steps
            fast = fast.next.next; 

            // Step 2: If the slow and fast
            // pointers meet, there is a loop
            if (slow == fast) {
                return findLength(slow, fast);
            }
        }

        // Step 3: If the fast pointer reaches the end
        // there is no loop
        
        return 0; 
    }


    public static void main(String[] args) {
        // Create a sample linked list with a loop
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);
        Node fifth = new Node(5);

        // Create a loop from fifth to second
        head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        // This creates a loop
        fifth.next = second; 

        int loopLength = lengthOfLoop(head);
        if (loopLength > 0) {
            System.out.println("Length of the loop: " + loopLength);
        } else {
            System.out.println("No loop found in the linked list.");
        }
    }
}


class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

# Function to detect a loop in a
# linked list using the Tortoise and Hare Algorithm

def detect_loop(head):
    # Initialize the slow pointer at the head
    slow = head  
    
     # Initialize the fast pointer at the head
    fast = head 

    # Step 1: Traverse the list to detect a loop
    while fast is not None and fast.next is not None:
        # Move slow one step
        slow = slow.next  
        # Move fast two steps
        fast = fast.next.next  

        # Step 2: If the slow and fast
        # pointers meet, there is a loop
        if slow == fast:
            return True

    # Step 3: If the fast pointer
    # reaches the end, there is no loop
    return False

# Function to find the length
# of the loop in a linked list
def find_loop_length(head):
    slow = head
    fast = head

    # Step 1: Traverse the list to detect a loop
    while fast is not None and fast.next is not None:
        # Move slow one step
        slow = slow.next     
        # Move fast two steps
        fast = fast.next.next  

        # Step 2: If the slow and fast
        # pointers meet, there is a loop
        if slow == fast:
            # Initialize the loop length
            length = 1  
             # Move fast one step
            fast = fast.next 

            # Step 4: Initialize a counter
            # and traverse using the fast pointer
            while slow != fast:
                # Move fast one step
                fast = fast.next  
                # Increment the counter
                length += 1  

            # Step 6: Return the 
            # length of the loop
            return length

    # Step 3: If the fast pointer
    # reaches the end, there is no loop
    return 0  

# Create a linked list with a loop for testing
head = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)

head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3  # Creating a loop

# Check if there is a loop in the linked list
if detect_loop(head):
    # If there is a loop, find its length
    length = find_loop_length(head)
    print(f"The length of the loop is: {length}")
else:
    print("No loop found in the linked list.")


function Node(data1, next1) {
    // Data stored in the node
    this.data = data1;
    // Pointer to the next node
    // in the list
    this.next = next1 || null;
}

// Function to return the lenght
// of loop when slow and fast are
// on the same node
function findLength(slow, fast) {
    // count to keep track of 
    // nodes encountered in loop
    let cnt = 1;

    // move fast by one step
    fast = fast.next;
    
    // traverse fast till it 
    // reaches back to slow
    while (slow !== fast) {
        
        // at each node increase
        // count by 1 and move fast
        // forward by one step
        cnt++;
        fast = fast.next;
    }
    
    // loop terminates when fast reaches
    // slow again and the count is returned

    return cnt;
}

// Function to find the length
// of the loop in a linked list
function lengthOfLoop(head) {
    let slow = head;
    let fast = head;

    // Step 1: Traverse the list to detect a loop
    while (fast !== null && fast.next !== null) {
        // Move slow one step
        slow = slow.next;

        // Move fast two steps
        fast = fast.next.next;

        // Step 2: If the slow and fast pointers
        // meet, there is a loop
        if (slow === fast) {
            // return the number of nodes
            // in the loop
            return findLength(slow, fast);
        }
    }
    
    // Step 3: If the fast pointer
    // reaches the end, there is no loop
    return 0;
}

// Create a sample linked list with a loop
var head = new Node(1);
var second = new Node(2);
var third = new Node(3);
var fourth = new Node(4);
var fifth = new Node(5);

// Create a loop from fifth to second
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;

// This creates a loop
fifth.next = second;

var loopLength = lengthOfLoop(head);

if (loopLength > 0) {
    console.log("Length of the loop:", loopLength);
} else {
    console.log("No loop found in the linked list.");
}

Output: Length of the loop: 4

Complexity Analysis

Time Complexity: O(N) The code traverses the entire linked list once, where ‘n’ is the number of nodes in the list. This traversal has a linear time complexity, O(n).

Space Complexity: O(1) The code uses only a constant amount of additional space, regardless of the linked list’s length. This is achieved by using two pointers (slow and fast) to detect the loop without any significant extra memory usage, resulting in constant space complexity, O(1).

Video Explanation

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article