Find length of a loop in Linked List using map in C++

In this tutorial, we will learn how to find length of a loop in Linked List in C++ using map.

The objective is to check if in a given Linked List there is a loop if the loop is present print the number of nodes between the starting and end of the loop in C++.

Objective and Approach

We need to find the length of the loop in the linked list. If no loop is present print 0. As in the example below the length of the loop is 6.

Find length of a loop in Linked List using map in C++

We will use Map to store the address of nodes while iterating through the linked list as key and their position as values.

Steps:

  • Traverse all the nodes and store start as 1 and increment after every node.
  • Check whether the node is present in the Map or not.
    • If the address of the current node is not present in the map insert the value in the map along with its position
    • If the address of the current node is present than print the difference between their positions.
  • If not found print 0.

Full Implementation:

//author @Nishant

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

class Node{
    public:
        int data;
        struct Node* next;
    
        Node(int num){
            data = num;
            next = NULL;
        }
};

int countLengthOfLoop(Node *head);

int main(){
    // Constructing a Linked List
    Node *head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = new Node(6);
    head->next->next->next->next->next->next = new Node(7);

    // Creating a loop to test the function
    head->next->next->next->next->next->next->next = head->next;

    // Printing length of loop in linked list
    if(countLengthOfLoop){
        cout << "Lenght of loop is " << countLengthOfLoop(head);
    }else{
        cout << "No Loop found in linked List";
    }
    cout << endl;

    return 0;
}

int countLengthOfLoop(Node *head){
    Node *temp = head;
    int position = 0;

    // Map to store Node and it's address
    unordered_map<Node*, int> mp;

    //traversing the linked list
    while(temp != NULL){
        // If not present in map
        if(mp.find(temp) == mp.end()){
            mp[temp] = position;
            position++;
        }else{ // If present in map
            return (position - mp[temp]);
        }
        temp = temp->next;
    }
    // If no loop is found
    return 0;
}

Output:

Lenght of loop is 6

Also read: Traversal in a Circular Linked List in C++

Leave a Reply

Your email address will not be published. Required fields are marked *