Count duplicates in a given linked list
Given a linked list. The task is to count the number of duplicate nodes in the linked list.
Examples:
Input: 5 -> 7 -> 5 -> 1 -> 7 -> NULL
Output: 2
Input: 5 -> 7 -> 8 -> 7 -> 1 -> NULL
Output: 1
Simple Approach: We traverse the whole linked list. For each node we check in the remaining list whether the duplicate node exists or not. If it does then we increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <unordered_set> using namespace std; // Representation of node struct Node { int data; Node* next; }; // Function to insert a node at the beginning void insert(Node** head, int item) { Node* temp = new Node(); temp->data = item; temp->next = *head; *head = temp; } // Function to count the number of // duplicate nodes in the linked list int countNode(Node* head) { int count = 0; while (head->next != NULL) { // Starting from the next node Node *ptr = head->next; while (ptr != NULL) { // If some duplicate node is found if (head->data == ptr->data) { count++; break ; } ptr = ptr->next; } head = head->next; } // Return the count of duplicate nodes return count; } // Driver code int main() { Node* head = NULL; insert(&head, 5); insert(&head, 7); insert(&head, 5); insert(&head, 1); insert(&head, 7); cout << countNode(head); return 0; } |
Java
// Java implementation of the approach class GFG { // Representation of node static class Node { int data; Node next; }; // Function to insert a node at the beginning static Node insert(Node head, int item) { Node temp = new Node(); temp.data = item; temp.next = head; head = temp; return head; } // Function to count the number of // duplicate nodes in the linked list static int countNode(Node head) { int count = 0 ; while (head.next != null ) { // Starting from the next node Node ptr = head.next; while (ptr != null ) { // If some duplicate node is found if (head.data == ptr.data) { count++; break ; } ptr = ptr.next; } head = head.next; } // Return the count of duplicate nodes return count; } // Driver code public static void main(String args[]) { Node head = null ; head = insert(head, 5 ); head = insert(head, 7 ); head = insert(head, 5 ); head = insert(head, 1 ); head = insert(head, 7 ); System.out.println( countNode(head)); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach import math # Representation of node class Node: def __init__( self , data): self .data = data self . next = None # Function to push a node at the beginning def push(head, item): temp = Node(item); temp.data = item; temp. next = head; head = temp; return head; # Function to count the number of # duplicate nodes in the linked list def countNode(head): count = 0 while (head. next ! = None ): # print(1) # Starting from the next node ptr = head. next while (ptr ! = None ): # print(2) # If some duplicate node is found if (head.data = = ptr.data): count = count + 1 break ptr = ptr. next head = head. next # Return the count of duplicate nodes return count # Driver code if __name__ = = '__main__' : head = None ; head = push(head, 5 ) head = push(head, 7 ) head = push(head, 5 ) head = push(head, 1 ) head = push(head, 7 ) print (countNode(head)) # This code is contributed by Srathore |
C#
// C# implementation of the approach using System; class GFG { // Representation of node public class Node { public int data; public Node next; }; // Function to insert a node at the beginning static Node insert(Node head, int item) { Node temp = new Node(); temp.data = item; temp.next = head; head = temp; return head; } // Function to count the number of // duplicate nodes in the linked list static int countNode(Node head) { int count = 0; while (head.next != null ) { // Starting from the next node Node ptr = head.next; while (ptr != null ) { // If some duplicate node is found if (head.data == ptr.data) { count++; break ; } ptr = ptr.next; } head = head.next; } // Return the count of duplicate nodes return count; } // Driver code public static void Main(String []args) { Node head = null ; head = insert(head, 5); head = insert(head, 7); head = insert(head, 5); head = insert(head, 1); head = insert(head, 7); Console.WriteLine( countNode(head)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach // Representation of a node class Node { constructor() { var data; var next; } } // Function to insert a node at the beginning function insert( head, item) { var temp = new Node(); temp.data = item; temp.next = head; head = temp; return head; } // Function to count the number of // duplicate nodes in the linked list function countNode( head) { let count = 0; while (head.next != null ) { // Starting from the next node let ptr = head.next; while (ptr != null ) { // If some duplicate node is found if (head.data == ptr.data) { count++; break ; } ptr = ptr.next; } head = head.next; } // Return the count of duplicate nodes return count; } // Driver Code var head = null ; head = insert(head, 5); head = insert(head, 7); head = insert(head, 5); head = insert(head, 1); head = insert(head, 7); document.write( countNode(head)); // This code is contributed by jana_ayantan. </script> |
Output:
2
Time Complexity: O(n*n)
Efficient Approach: The idea is to use hashing
C++
// C++ implementation of the approach #include <iostream> #include <unordered_set> using namespace std; // Representation of node struct Node { int data; Node* next; }; // Function to insert a node at the beginning void insert(Node** head, int item) { Node* temp = new Node(); temp->data = item; temp->next = *head; *head = temp; } // Function to count the number of // duplicate nodes in the linked list int countNode(Node* head) { if (head == NULL) return 0;; // Create a hash table insert head unordered_set< int > s; s.insert(head->data); // Traverse through remaining nodes int count = 0; for (Node *curr=head->next; curr != NULL; curr=curr->next) { if (s.find(curr->data) != s.end()) count++; s.insert(curr->data); } // Return the count of duplicate nodes return count; } // Driver code int main() { Node* head = NULL; insert(&head, 5); insert(&head, 7); insert(&head, 5); insert(&head, 1); insert(&head, 7); cout << countNode(head); return 0; } |
Java
// Java implementation of the approach import java.util.HashSet; class GFG { // Representation of node static class Node { int data; Node next; }; static Node head; // Function to insert a node at the beginning static void insert(Node ref_head, int item) { Node temp = new Node(); temp.data = item; temp.next = ref_head; head = temp; } // Function to count the number of // duplicate nodes in the linked list static int countNode(Node head) { if (head == null ) return 0 ;; // Create a hash table insert head HashSet<Integer>s = new HashSet<>(); s.add(head.data); // Traverse through remaining nodes int count = 0 ; for (Node curr=head.next; curr != null ; curr=curr.next) { if (s.contains(curr.data)) count++; s.add(curr.data); } // Return the count of duplicate nodes return count; } // Driver code public static void main(String[] args) { insert(head, 5 ); insert(head, 7 ); insert(head, 5 ); insert(head, 1 ); insert(head, 7 ); System.out.println(countNode(head)); } } // This code is contributed by Princi Singh |
Python
# Python3 implementation of the approach # Node of a linked list class Node: def __init__( self , data = None , next = None ): self . next = next self .data = data head = None # Function to insert a node at the beginning def insert(ref_head, item): global head temp = Node() temp.data = item temp. next = ref_head head = temp # Function to count the number of # duplicate nodes in the linked list def countNode(head): if (head = = None ): return 0 # Create a hash table insert head s = set () s.add(head.data) # Traverse through remaining nodes count = 0 curr = head. next while ( curr ! = None ) : if (curr.data in s): count = count + 1 s.add(curr.data) curr = curr. next # Return the count of duplicate nodes return count # Driver code insert(head, 5 ) insert(head, 7 ) insert(head, 5 ) insert(head, 1 ) insert(head, 7 ) print (countNode(head)) # This code is contributed by Arnab Kundu |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Representation of node public class Node { public int data; public Node next; }; static Node head; // Function to insert a node at the beginning static void insert(Node ref_head, int item) { Node temp = new Node(); temp.data = item; temp.next = ref_head; head = temp; } // Function to count the number of // duplicate nodes in the linked list static int countNode(Node head) { if (head == null ) return 0;; // Create a hash table insert head HashSet< int >s = new HashSet< int >(); s.Add(head.data); // Traverse through remaining nodes int count = 0; for (Node curr=head.next; curr != null ; curr=curr.next) { if (s.Contains(curr.data)) count++; s.Add(curr.data); } // Return the count of duplicate nodes return count; } // Driver code public static void Main(String[] args) { insert(head, 5); insert(head, 7); insert(head, 5); insert(head, 1); insert(head, 7); Console.WriteLine(countNode(head)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach // Representation of node class Node { constructor() { this .data = 0; this .next = null ; } }; // Function to insert a node at the beginning function insert(head, item) { var temp = new Node(); temp.data = item; temp.next = head; head = temp; return head; } // Function to count the number of // duplicate nodes in the linked list function countNode(head) { if (head == null ) return 0;; // Create a hash table insert head var s = new Set(); s.add(head.data); // Traverse through remaining nodes var count = 0; for ( var curr=head.next; curr != null ; curr=curr.next) { if (s.has(curr.data)) count++; s.add(curr.data); } // Return the count of duplicate nodes return count; } // Driver code var head = null ; head = insert(head, 5); head = insert(head, 7); head = insert(head, 5); head = insert(head, 1); head = insert(head, 7); document.write( countNode(head)); </script> |
Output:
2
Time Complexity : O(n)