# 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 ^{2})**.

**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)**.