Write a program that checks whether a given Linked List contains a loop and if a loop is present then returns the count of nodes in the loop. For example, a loop is present in the below-linked list and the length of the loop is 4. If the loop is not present, then the function should return 0.
Approach: In this post, we will use the concept of Map to store the addresses of nodes present in the linked list as a key and their position as the values.
Below is the step-by-step approach:
- Traverse every node of the linked list and maintain the position starting with one. Increment the position after every node.
- Check whether that node is present in the Map or not.
- If the map does not contain the address of that node, insert it into the map along with its position.
- If the map already contains the address of that node, return the difference between their positions.
- If no such node has been found, return 0.
Below is the implementation of the above approach:
C++
// C++ program to find length of loop// in a linked list using Map#include <bits/stdc++.h>using namespace std;// Linked List nodestruct Node { int data; struct Node* next; Node(int num) { data = num; next = NULL; }};// Function detects and counts loop// nodes in the list. If loop is not there,// then returns 0int countNodesinLoop(struct Node* head){ struct Node* p = head; int pos = 0; // Maintain a map to store addresses // of node and their position unordered_map<Node*, int> m; // Traverse through the linked list while (p != NULL) { // If the node is not present in the map if (m.find(p) == m.end()) { m[p] = pos; pos++; } // if the node is present else { // Return difference between // position of the present node and // position where that node occurred before return (pos - m[p]); } p = p->next; } // Return 0 to indicate // there is no loop return 0;}// Driver codeint main(){ // Create nodes of the linked list struct 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); // Create a loop for testing the function head->next->next->next->next->next = head->next; // Call the function for the above linked list cout << countNodesinLoop(head) << endl; return 0;} |
Java
// Java program to find length of loop// in a linked list using Mapimport java.util.*;import java.io.*;class GFG{ static class Node { int data; Node next; // Constructor Node(int num) { data = num; next = null; } } // Function detects and counts loop// nodes in the list. If loop is not there,// then returns 0public static int countNodesinLoop(Node head){ Node p = head; int pos = 0; // Maintain a map to store addresses // of node and their position HashMap<Node, Integer> m = new HashMap<Node, Integer>(); // Traverse through the linked list while (p != null) { // If the node is not present in the map if (!m.containsKey(p)) { m.put(p, pos); pos++; } // If the node is present else { // Return difference between // position of the present // node and position where // that node occurred before return (pos - m.get(p)); } p = p.next; } // Return 0 to indicate // there is no loop return 0;} // Driver codepublic static void main (String[] args) { // Create nodes of the 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); // Create a loop for testing the function head.next.next.next.next.next = head.next; // Call the function for the above linked list System.out.println(countNodesinLoop(head));}}// This code is contributed by adityapande88 |
Python3
# Python3 program to find length of loop# in a linked list using Map # Linked List nodeclass Node: def __init__(self, data): self.data = data self.next = None # Function detects and counts loop# nodes in the list. If loop is not there,# then returns 0def countNodesinLoop(head): p = head; pos = 0; # Maintain a map to store addresses # of node and their position m = dict() # Traverse through the linked list while (p != None): # If the node is not present in the map if (p not in m): m[p] = pos; pos += 1 # if the node is present else: # Return difference between # position of the present node and # position where that node occurred before return (pos - m[p]); p = p.next; # Return 0 to indicate # there is no loop return 0; # Driver codeif __name__=='__main__': # Create nodes of the linked list head = Node(1); head.next = Node(2); head.next.next = Node(3); head.next.next.next = Node(4); head.next.next.next.next = Node(5); # Create a loop for testing the function head.next.next.next.next.next = head.next; # Call the function for the above linked list print(countNodesinLoop(head)) # This code is contributed by Pratham76 |
C#
// C# program to find length of loop// in a linked list using Mapusing System;using System.Collections;using System.Collections.Generic; class GFG{ public class Node { public int data; public Node next; // Constructor public Node(int num) { data = num; next = null; } } // Function detects and counts loop// nodes in the list. If loop is not there,// then returns 0public static int countNodesinLoop(Node head){ Node p = head; int pos = 0; // Maintain a map to store addresses // of node and their position Dictionary<Node, int> m = new Dictionary<Node, int>(); // Traverse through the linked list while (p != null) { // If the node is not present in the map if (!m.ContainsKey(p)) { m[p] = pos; pos++; } // If the node is present else { // Return difference between // position of the present // node and position where // that node occurred before return (pos - m[p]); } p = p.next; } // Return 0 to indicate // there is no loop return 0;} // Driver codepublic static void Main(string[] args) { // Create nodes of the 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); // Create a loop for testing the function head.next.next.next.next.next = head.next; // Call the function for the above linked list Console.Write(countNodesinLoop(head));}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program to find length of loop// in a linked list using Map// Linked List nodeclass Node { constructor(num) { this.data = num; this.next = null; }};// Function detects and counts loop// nodes in the list. If loop is not there,// then returns 0function countNodesinLoop(head){ var p = head; var pos = 0; // Maintain a map to store addresses // of node and their position var m = new Map(); // Traverse through the linked list while (p != null) { // If the node is not present in the map if (!m.has(p)) { m.set(p, pos); pos++; } // if the node is present else { // Return difference between // position of the present node and // position where that node occurred before return (pos - m.get(p)); } p = p.next; } // Return 0 to indicate // there is no loop return 0;}// Driver code// Create nodes of the linked listvar 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);// Create a loop for testing the functionhead.next.next.next.next.next = head.next;// Call the function for the above linked listdocument.write( countNodesinLoop(head));// This code is contributed by noob2000.</script> |
Output
4
Time Complexity: O(n) where n is size of linked list
Auxiliary Space: O(n)
Similar Article: Find the length of a loop in a Linked list using Floyd’s Cycle detection algorithm
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
