# Count duplicates in a Linked list

Aman Chourasiya
Last Updated: May 13, 2022

## 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

1. Create a function countDuplicates which takes the head of a linked list as an argument.
3. 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.
4. Return the count.

### 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

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

## Program

### 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!