Length of loop in LL

Intuition

First, detect the loop in the linked list, then count the nodes within the loop to determine its length.

Approach

While traversing the linked list, use a timer to count the number of nodes visited. Assign each node a timer value when it is first encountered. If you visit a node that has already been encountered, you can determine the length of the loop by subtracting the timer value from when the node was first visited from the current timer value. This requires keeping track of each node and its associated timer value, which can be done using a hashmap where nodes are the keys and their timer values are the values.

Below is the algorithm for the approach

Start at the head of the linked list and use a temporary pointer to traverse the list. Move through each node until you reach the end (null). During traversal, store each visited node along with a timer value in a hashmap to track the nodes and their visit times.
As you continue traversing, if you encounter a node that is already in the hashmap, a loop is detected. The length of the loop is determined by subtracting the timer value of the first visit from the current timer value.
If the traversal completes and you reach null, it indicates that there is no loop in the linked list. In this case, return 0 to signify no loop found.

Dry Run

Solution

#include <bits/stdc++.h>

using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to find length
    int findLengthOfLoop(ListNode *head) {
        // Hashmap to store visited nodes and their timer values
        unordered_map<ListNode*, int> visitedNodes;

        // Initialize pointer to traverse the linked list
        ListNode* 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 difference of timer values
            if (visitedNodes.find(temp) != visitedNodes.end()) {
                // Calculate the length of the loop
                int loopLength = timer - visitedNodes[temp];

                // Return length of 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
    ListNode* head = new ListNode(1);
    ListNode* second = new ListNode(2);
    ListNode* third = new ListNode(3);
    ListNode* fourth = new ListNode(4);
    ListNode* fifth = new ListNode(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;

    Solution solution;
    int loopLength = solution.findLengthOfLoop(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.io.*;

// Definition of singly linked list:
class ListNode {
    int val;
    ListNode next;

    ListNode() {
        val = 0;
        next = null;
    }

    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to find length
    public int findLengthOfLoop(ListNode head) {
        // HashMap to store visited nodes and their timer values
        HashMap<ListNode, Integer> visitedNodes = new HashMap<>();

        // Initialize pointer to traverse the linked list
        ListNode 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 difference of timer values
            if (visitedNodes.containsKey(temp)) {
                // Calculate the length of the loop
                int loopLength = timer - visitedNodes.get(temp);

                // Return length of 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 sample linked list with a loop
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode fourth = new ListNode(4);
        ListNode fifth = new ListNode(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;

        Solution solution = new Solution();
        int loopLength = solution.findLengthOfLoop(head);
        if (loopLength > 0) {
            System.out.println("Length of the loop: " + loopLength);
        } else {
            System.out.println("No loop found in the linked list.");
        }
    }
}
# Definition of singly linked list:
 class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
         self.next = next

class Solution:
    def findLengthOfLoop(self, head):
        # Dictionary to store visited nodes and their timer values
        visited_nodes = {}

        # Initialize pointer to traverse the linked list
        temp = head

        # Initialize timer 
        # to track visited nodes
        timer = 0

        # Traverse the linked list 
        # till temp reaches None
        while temp is not None:
            # If revisiting a node return difference of timer values
            if temp in visited_nodes:
                # Calculate the length of the loop
                loop_length = timer - visited_nodes[temp]

                # Return length of loop
                return loop_length
            # Store the current node 
            # and its timer value in 
            # the dictionary
            visited_nodes[temp] = timer

            # Move to the next node
            temp = temp.next

            # Increment the timer
            timer += 1

        # If traversal is completed 
        # and we reach the end 
        # of the list (None)
        # means there is no loop
        return 0

# Sample linked list with a loop
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

head = ListNode(1)
second = ListNode(2)
third = ListNode(3)
fourth = ListNode(4)
fifth = ListNode(5)

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

solution = Solution()
loop_length = solution.findLengthOfLoop(head)
if loop_length > 0:
    print("Length of the loop:", loop_length)
else:
    print("No loop found in the linked list.")
// Definition of singly linked list:
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to find length
    findLengthOfLoop(head) {
        // Map to store visited nodes and their timer values
        const visitedNodes = new Map();

        // Initialize pointer to traverse the linked list
        let temp = head;

        // Initialize timer 
        // to track visited nodes
        let timer = 0;

        // Traverse the linked list 
        // till temp reaches null
        while (temp !== null) {
            // If revisiting a node return 
            // difference of timer values
            if (visitedNodes.has(temp)) {
                // Calculate the length of the loop
                const loopLength = timer - visitedNodes.get(temp);

                // Return length of loop
                return loopLength;
            }
            /* Store the current node 
            and its timer value in 
            the Map */
            visitedNodes.set(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;
    }
}

// Sample linked list with a loop
const head = new ListNode(1);
const second = new ListNode(2);
const third = new ListNode(3);
const fourth = new ListNode(4);
const fifth = new ListNode(5);

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

const solution = new Solution();
const loopLength = solution.findLengthOfLoop(head);
if (loopLength > 0) {
    console.log("Length of the loop:", loopLength);
} else {
    console.log("No loop found in the linked list.");
}

Complexity Analysis

Time Complexity: O(N) because the code traverses the entire linked list at least once, where 'N' is the number of nodes in the list.

Space Complexity: O(N) because 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.

Intuition

The brute force method uses O(N) additional memory. To improve efficiency, the Tortoise and Hare approach is introduced as an optimized method because it detects loops using constant space. This approach uses two pointers moving at different speeds, ensuring that if a loop exists, they will meet within the loop, allowing detection without extra memory.

Approach

Begin with two pointers, slow and fast, both starting at the head of the linked list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.

Move slow one step and fast two steps at a time until fast or next of fast is null (indicating no loop) or slow meets fast (indicating a loop). If slow and fast meet, this confirms a loop.

Then, initialize a counter and move fast one step at a time while incrementing the counter. Continue until fast meets slow again; the counter value at this point represents the length of the loop.

Dry Run

Loop Detection

Calculating the length

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to find the length of the loop 
    int findLength(ListNode* slow, ListNode* 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
            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 
    int findLengthOfLoop(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // 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;

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

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

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

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

    Solution solution;
    int loopLength = solution.findLengthOfLoop(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.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
        val = 0;
        next = null;
    }

    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}

class Solution {
    // Function to find the length of the loop
    int findLength(ListNode slow, ListNode 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
            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
    public int findLengthOfLoop(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // 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;

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

        /* 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
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode fourth = new ListNode(4);
        ListNode fifth = new ListNode(5);

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

        Solution solution = new Solution();
        int loopLength = solution.findLengthOfLoop(head);
        if (loopLength > 0) {
            System.out.println("Length of the loop: " + loopLength);
        } else {
            System.out.println("No loop found in the linked list.");
        }
    }
}
# Definition of singly linked list:
class ListNode:
    def __init__(self, val=0, next=None):
         self.val = val
         self.next = next

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to find the length of the loop
    def findLength(self, 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
            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
    def findLengthOfLoop(self, head):
        slow = head
        fast = head

        # 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

            # If the slow and fast pointers meet
            # there is a loop
            if slow == fast:
                # return the number of nodes 
                return self.findLength(slow, fast)

        """ If the fast pointer 
        reaches the end, 
        there is no loop """
        return 0

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

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

solution = Solution()
loopLength = solution.findLengthOfLoop(head)
if loopLength > 0:
    print("Length of the loop:", loopLength)
else:
    print("No loop found in the linked list.")
// Definition of singly linked list:
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to find the length of the loop
    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
            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
    findLengthOfLoop(head) {
        let slow = head;
        let fast = head;

        // 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;

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

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

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

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

const solution = new Solution();
const loopLength = solution.findLengthOfLoop(head);
if (loopLength > 0) {
    console.log("Length of the loop:", loopLength);
} else {
    console.log("No loop found in the linked list.");
}

Complextiy Analysis

Time Complexity: O(N) because the code traverses the entire linked list once, where 'N' is the number of nodes in the list.

Space Complexity: O(1) because 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).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Below is the algorithm for the approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Loop Detection

Calculating the length

Solution

Complextiy Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts