Count duplicates in a given circular linked list
Given a circular linked list, the task is to check whether the given list has duplicates or not.
Example:
Input: list = {5, 7, 5, 1, 4, 4}
Output: 2
Explanation: The given list has 2 indices having integers which has already occurred in the list during traversal.Input: list = {1, 1, 1, 1, 1}
Output: 4
Approach: The given problem has a very similar solution to finding the count of duplicates in a linked list. The idea is to use hashing. Traverse the given circular linked list using the algorithm discussed here. Create a hashmap to store the integers that occurred in the list and for each integer, check if the integer has already occurred. Maintain the count of already occurred integers in a variable.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Class to store Node of the list class Node { public : int data; Node* next; Node( int data) { this ->data = data; this ->next = NULL; } }; // Function to find the count of the // duplicate integers in the list static int checkDuplicate(Node* head) { if (head == NULL) return 0; // Stores the count of duplicate // integers int cnt = 0; // Stores the integers occurred set< int > s; s.insert(head->data); Node *curr = head->next; // Loop to traverse the given list while (curr != head) { // If integer already occurred if (s.find(curr->data) != s.end()) cnt++; // Add current integer into // the hashmap s.insert(curr->data); curr = curr->next; } // Return answer return cnt; } // Driver Code int main() { Node *head = new Node(5); head->next = new Node(7); head->next->next = new Node(5); head->next->next->next = new Node(1); head->next->next->next->next = new Node(4); head->next->next->next->next->next = new Node(4); head->next->next->next->next->next->next = head; cout << checkDuplicate(head) << endl; return 0; } // This code is contributed by Dharanendra L V. |
Java
// Java program for the above approach import java.util.HashSet; public class GFG { // Class to store Node of the list static class Node { public int data; public Node next; public Node( int data) { this .data = data; } } // Stores head pointer of the list static Node head; // Function to find the count of the // duplicate integers in the list static int checkDuplicate(Node head) { if (head == null ) return 0 ; // Stores the count of duplicate // integers int cnt = 0 ; // Stores the integers occurred HashSet<Integer> s = new HashSet<Integer>(); s.add(head.data); Node curr = head.next; // Loop to traverse the given list while (curr != head) { // If integer already occurred if (s.contains(curr.data)) cnt++; // Add current integer into // the hashset s.add(curr.data); curr = curr.next; } // Return answer return cnt; } // Driver Code public static void main(String[] args) { head = new Node( 5 ); head.next = new Node( 7 ); head.next.next = new Node( 5 ); head.next.next.next = new Node( 1 ); head.next.next.next.next = new Node( 4 ); head.next.next.next.next.next = new Node( 4 ); head.next.next.next.next.next.next = head; System.out.println(checkDuplicate(head)); } } // this code is contributed by bhardwajji |
Python3
# Python program for the above approach # Class to store Node of the list class Node: def __init__( self , data): self .data = data; self . next = None ; # Stores head pointer of the list head = None ; # Function to find the count of the # duplicate integers in the list def checkDuplicate(head): if (head = = None ): return 0 ; # Stores the count of duplicate # integers cnt = 0 ; # Stores the integers occurred s = set (); s.add(head.data); curr = head. next ; # Loop to traverse the given list while (curr ! = head): # If integer already occurredA if ((curr.data) in s): cnt + = 1 ; # Add current integer into # the hashmap s.add(curr.data); curr = curr. next ; # Return answer return cnt; # Driver Code if __name__ = = '__main__' : head = Node( 5 ); head. next = Node( 7 ); head. next . next = Node( 5 ); head. next . next . next = Node( 1 ); head. next . next . next . next = Node( 4 ); head. next . next . next . next . next = Node( 4 ); head. next . next . next . next . next . next = head; print (checkDuplicate(head)); # This code is contributed by umadevi9616 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Class to store Node of the list class Node { public int data; public Node next; public Node( int data) { this .data = data; } }; // Stores head pointer of the list static Node head; // Function to find the count of the // duplicate integers in the list static int checkDuplicate(Node head) { if (head == null ) return 0; // Stores the count of duplicate // integers int cnt = 0; // Stores the integers occurred HashSet< int > s = new HashSet< int >(); s.Add(head.data); Node curr = head.next; // Loop to traverse the given list while (curr != head) { // If integer already occurred if (s.Contains(curr.data)) cnt++; // Add current integer into // the hashmap s.Add(curr.data); curr = curr.next; } // Return answer return cnt; } // Driver Code public static void Main() { head = new Node(5); head.next = new Node(7); head.next.next = new Node(5); head.next.next.next = new Node(1); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = head; Console.Write(checkDuplicate(head)); } } // This code is contributed by ipg2016107. |
Javascript
<script> // javascript program for the above approach // Class to store Node of the list class Node { constructor(val) { this .data = val; this .next = null ; } } // Stores head pointer of the list var head; // Function to find the count of the // duplicate integers in the list function checkDuplicate(head) { if (head == null ) return 0; // Stores the count of duplicate // integers var cnt = 0; // Stores the integers occurred var s = new Set(); s.add(head.data); var curr = head.next; // Loop to traverse the given list while (curr != head) { // If integer already occurred if (s.has(curr.data)) cnt++; // Add current integer into // the hashmap s.add(curr.data); curr = curr.next; } // Return answer return cnt; } // Driver Code head = new Node(5); head.next = new Node(7); head.next.next = new Node(5); head.next.next.next = new Node(1); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(4); head.next.next.next.next.next.next = head; document.write(checkDuplicate(head)); // This code is contributed by gauravrajput1 </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)