Count duplicates in a given linked list

Problem

You are given a linked list. Your task is to find out all the duplicates in it and print the count of nodes which has at least 1 duplicate.  Have a look at example.

Example

Input 1

5 -> 9 -> 5 -> 1 -> 9 -> NULL

Output 1

2

Explanation

Here we can see 5 has a duplicate and 9 has a duplicate in linked list. So, in total we have 2 nodes which has duplicates in linked list, so our answer would be 2.

Input 2

 5 -> 3 -> 8 -> 3 -> 1 -> NULL

Output 2

1

Explanation

Here, we can see 3 is the only element which has a duplicate in linked list. So, our answer would be 1.

Solution

Naive apporach

The simplest way to solve this problem is to traverse the whole linked list and for each element we'll traverse the rest of the linked list and see if there is any duplicate, if duplicate is found, we'll increment the duplicate couter.

Here is implementation of this approach.
 

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

// 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; 
} 

// Main function
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; 
} 

2

Time complexity of this approach would be O(n²). 

Efficient approach

For problems like this, in which we have to find duplicates in a list, we can use hashing. 

We will build a hash table and store the data into hash and for each element we'll check if that element exists in hash, if it does, we'll increment duplicate counter. Finally, duplicate counter will be our answer which we'll return from function.

Here is implementation of this approach.

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

// 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; 
} 

// Main Function
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; 
} 

2

Time complexity of this approach would be O(n).