Find length of Loop

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: ‘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: LinkedList: 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 for the loop.
 

Input: LinkedList: 5->4, c = 0
Output: 0
Explanation: There is no loop.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

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

Approach 01:

#include <iostream>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // Function to find the length of a loop in the linked list.
    int countNodesinLoop(Node *head) {
        int position = 0;
        unordered_map<Node*, int> nodePositionMap;

        while (head != nullptr) {
            // Check if the node has been visited before, indicating a loop
            if (nodePositionMap.find(head) != nodePositionMap.end()) {
                // Calculate the loop length by subtracting the stored position
                return position - nodePositionMap[head];
            } else {
                // Store the current node with its position
                nodePositionMap[head] = position++;
                head = head->next;
            }
        }

        // Return 0 if no loop is detected
        return 0;
    }
};

class Solution:
    # Function to find the length of a loop in the linked list.
    def countNodesInLoop(self, head):
        position = 0
        nodePositionMap = {}

        while head:
            if head in nodePositionMap:
                # Calculate the loop length by subtracting the stored position.
                return position - nodePositionMap[head]
            else:
                # Store the current node with its position.
                nodePositionMap[head] = position
                position += 1
                head = head.next

        # Return 0 if no loop is detected.
        return 0

Time Complexity

• Traversal of Nodes:

  Each node in the linked list is visited once until a loop is detected or the end of the list is reached. Therefore, the traversal takes \( O(\text{numNodes}) \) time, where numNodes is the total number of nodes in the linked list.

• Overall Time Complexity:

  The overall time complexity is \( O(\text{numNodes}) \), as the algorithm only involves traversing the list and storing nodes in a map.

Space Complexity

• Node Position Map:

  The unordered map nodePositionMap stores each node and its position until a loop is detected. In the worst case, if there is no loop, the map stores all nodes, leading to a space complexity of \( O(\text{numNodes}) \).

• Overall Space Complexity:

  The overall space complexity is \( O(\text{numNodes}) \), primarily due to the unordered map used to store nodes and their positions.