# Count duplicates in a Linked list

## Understanding

In this blog, we are going to take up a problem based on Linked lists. Linked lists are popularly asked data structures in coding assessments and interviews. There are various standard problems based on Linked lists, for example, reverse a Linked list, check if a linked list contains a cycle, etc. This blog will discuss a similar problem - counting the number of duplicated nodes in a linked list.

## The Problem Statement

Ninja has given you a linked list as input. Your task is to count the number of duplicate nodes in the linked list.

## Input

Linked list: 4 -> 8 -> 7 -> 5 -> 8 -> 7 -> 10 -> 4

## Output

Number of duplicate nodes: 3

## Explanation

In the given linked list, the values of the 5th, 6th, and 8th nodes are already present in the linked list before. Hence the output is 3.

## Approach 1

A straightforward approach would be to consider each node of the linked list one by one. Start from each node and move ahead in the linked list. If you encounter a node with the same value as the node in consideration, it would mean that the current node is duplicated. In such a case, increase the count by one and break.

### Algorithm

- Create a function countDuplicates which takes the head of a linked list as an argument.
- While head->next is not null, store head->next in node* current.
- Now traverse the linked list starting from the current node pointer. If you find a node with the value same as the current node pointer, increase the count by one and break.
- Return the count.

### Program

#include<bits/stdc++.h> using namespace std; // Representation of a linked list node. struct Node { int value; Node* next; }; Node* createnode(int value){ // function to create a linked list. node. Node* newnode = new Node(); newnode->value = value; newnode->next = NULL; return newnode; } // Function to insert a node at the end of the linked list. void insertNode(Node** head, int item, Node** rear) { Node* temp = createnode(item); // create the new node. if(*head == NULL){ // if the linked list is empty. *head = temp; *rear = temp; return; } (*rear)->next = temp; // insert the new node at the end of the linked list. *rear = (*rear)->next; // update the rear pointer. } // Function to count the number of duplicate nodes in the linked list. int countDuplicates(Node* head) { int count = 0; while (head->next != NULL) { // Starting from the next node. Node *current = head->next; while (current != NULL) { // If some duplicate node is found. if (head->value == current->value) { count++; // increase the count of duplicate nodes. break; } current = current->next; } head = head->next; } // Return the count of duplicate nodes. return count; } // Driver code int main() { // create the linked list. Node* head = NULL, *rear = NULL; // head and rear pointers hold the beginning and end of the linkedlist. insertNode(&head, 4, &rear); insertNode(&head, 8, &rear); insertNode(&head, 7, &rear); insertNode(&head, 5, &rear); insertNode(&head, 8, &rear); insertNode(&head, 7, &rear); insertNode(&head, 10, &rear); insertNode(&head, 4, &rear); cout << countDuplicates(head)<<endl; return 0; } |

### Input

Linked list: 4 -> 8 -> 7 -> 5 -> 8 -> 7 -> 10 -> 4

### Output

Number of duplicate nodes: 3

### Time Complexity

The time complexity of the above approach is O(n^2), as the program uses two nested while loops to count the number of duplicates.

### Space Complexity

The space complexity of the above approach is O(1), as we are using constant memory during runtime.

## Approach 2

This approach uses hashing to achieve the task in O(n) time. We can use unordered_set to keep track of the values that we have encountered so far. We can traverse the linked list from its beginning to end. When we visit a node, we will check if the node's value has been encountered before. If yes, increase the count by one. Otherwise, insert the value into the unordered_set.

### Algorithm

- Create a function countDuplicates which takes the head of a linked list as an argument.
- Create an unordered_set alreadyEncountered to store the elements as we traverse the linked list.
- Insert the value of the head node into alreadyEncountered. Update head as head->next.
- Start traversal of the linked list from the newly updated head node and check the following condition.
- If the value of the current node is present in alreadyEncountered, increase the count by one. Otherwise, insert the value into alreadyEncountered.
- Return count.

## Program

#include<bits/stdc++.h> using namespace std; // Representation of a linked list node. struct Node { int value; Node* next; }; Node* createnode(int value){ // function to create a linked list node. Node* newnode = new Node(); newnode->value = value; newnode->next = NULL; return newnode; } // Function to insert a node at the end of the linked list. void insertNode(Node** head, int item, Node** rear) { Node* temp = createnode(item); // create the new node. if(*head == NULL){ // if the linked list is empty. *head = temp; *rear = temp; return; } (*rear)->next = temp; // insert the new node at the end of the linked list. *rear = (*rear)->next; // update the rear pointer. } // Function to count the number of duplicate nodes in the linked list. int countDuplicates(Node* head) { int count = 0; if(head == NULL) return 0; unordered_set<int> alreadyEncountered; alreadyEncountered.insert(head->value); // insert the head value. head = head->next; // move to the next node as head is already considered. while (head != NULL) { if(alreadyEncountered.find(head->value) != alreadyEncountered.end()){ // check if the current value is already present or not. alreadyEncountered.insert(head->value); } else count++; head=head->next; } // Return the count of duplicate nodes. return count; } // Driver code int main() { // create the linked list. Node* head = NULL, *rear = NULL; // head and rear pointers hold the beginning and end of the linkedlist. insertNode(&head, 4, &rear); insertNode(&head, 8, &rear); insertNode(&head, 7, &rear); insertNode(&head, 5, &rear); insertNode(&head, 8, &rear); insertNode(&head, 7, &rear); insertNode(&head, 10, &rear); insertNode(&head, 4, &rear); cout << countDuplicates(head)<<endl; return 0; } |

### Input

Linked list: 4 -> 8 -> 7 -> 5 -> 8 -> 7 -> 10 -> 4

### Output

Number of duplicate nodes: 3

### Time Complexity

The time complexity of the above approach is **O(n)**, as the program uses the find function of unordered_set (defined in C++ STL), which has O(1) time complexity. Since we make n such calls, the total time complexity is O(n).

### Space Complexity

The space complexity of the above approach is **O(n)**, as the size of the unordered_set can grow to the order of n when all the nodes have unique values.

## Key Takeaways

This blog discussed two approaches for counting the number of duplicate nodes in a linked list. The first approach used a brute force method to solve the problem, while the second one involved using a specific data structure defined in C++. We could also use set in place of unordered_set. But in that case, the time complexity would become O(NlogN) as the find function of the set container has O(logN) time complexity.

Yet learning never stops, and there is a lot more to learn.

So head over to our practice platform __CodeStudio__ to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Comments

## No comments yet

## Be the first to share what you think