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.
  2. While head->next is not null, store head->next in node* current.
  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.

 

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

  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.
  3. Insert the value of the head node into alreadyEncountered. Update head as head->next.
  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

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think