Master How to Count Duplicates in a Linked List (2026)

Learn how to count duplicates in a linked list in C++ with this beginner-friendly guide. Step-by-step explanation, easy-to-understand code, and tips for detecting duplicate nodes efficiently.

Linked lists are one of the fundamental data structures in programming. While they are simple to understand, performing operations like counting duplicates can be tricky for beginners. In this guide, we will explain how to count duplicates in a linked list in an easy-to-understand, step-by-step way.

What is a Linked List?

A linked list is a collection of nodes where each node contains two things:

1. Data – The value stored in the node.
2. Pointer (Next) – A reference to the next node in the list.

For example, a linked list can look like this:

1 → 2 → 2 → 3 → 3 → 3 → 4

What Are Duplicates in a Linked List?

Duplicates are values that appear more than once in the linked list.

In the example above:

• 2 appears twice → 1 duplicate
• 3 appears three times → 2 duplicates

Total duplicates = 3

Step-By-Step Approach to Count Duplicates

Here’s a simple way to count duplicates, perfect for beginners:

1. Start with the first node (curr).
2. Compare it with all nodes that come after it (temp).
3. If a node has the same value as curr, it’s a duplicate.
4. Move to the next node and repeat until the end.

Understanding the Key Line: Node* temp = curr->next;

One line often confuses beginners:

Node* temp = curr->next;

Here’s what it means:

• Node* temp → temp is a pointer that can point to a node.
• curr->next → the next node after the current node.
• Together → temp starts checking from the node after curr, not from the beginning. This avoids counting the same value multiple times.

Count Duplicates in a Linked List : C++ Code

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

// Function to count duplicates
int countDuplicates(Node* head) {
    int count = 0;
    Node* curr = head;

    while (curr != NULL) {
        Node* temp = curr->next; // Start checking from next node

        while (temp != NULL) {
            if (curr->data == temp->data) {
                count++;
                break; // Count only once per value
            }
            temp = temp->next;
        }
        curr = curr->next;
    }

    return count;
}

// Main function
int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(2);
    head->next->next->next = new Node(3);
    head->next->next->next->next = new Node(3);
    head->next->next->next->next->next = new Node(3);
    head->next->next->next->next->next->next = new Node(4);

    cout << "Total duplicate nodes: " << countDuplicates(head) << endl;
    return 0;
}

How This Works

1. curr pointer moves node by node.
2. temp pointer checks all nodes after curr.
3. If curr->data == temp->data, we found a duplicate.
4. Count is updated once per duplicate value.

Time and Space Complexity

• Time Complexity: O(n²) – two nested loops
• Space Complexity: O(1) – no extra memory used

Note: For beginners, this approach is easy to understand. Advanced methods (like using a hash map) can reduce time complexity.

Time Complexity

Answer:

Time Complexity = O(n²)

Why O(n²)? (How we calculate it)

Look at this part of the code:

while (curr != NULL) {          // Outer loop
    Node* temp = curr->next;

    while (temp != NULL) {      // Inner loop
        if (curr->data == temp->data) {
            count++;
            break;
        }
        temp = temp->next;
    }
    curr = curr->next;
}

Step-by-step thinking

• Let total number of nodes = n

Outer loop (curr)

• Runs for every node
• So it runs n times

Inner loop (temp)

• For each curr, it checks the remaining nodes
• In worst case:
  • First time → checks ~ (n-1) nodes
  • Second time → checks ~ (n-2) nodes
  • …
  • Last time → checks 1 node

Total comparisons (worst case)

(n-1) + (n-2) + (n-3) + ... + 1

This adds up to:

n² (approximately)

That’s why Time Complexity = O(n²)

Simple line to remember (for exams/interviews)

Since there are two nested loops, the time complexity is O(n²).

Space Complexity

Answer:

Space Complexity = O(1)

Why O(1)? (How we calculate it)

Let’s see what extra memory we use:

int count;
Node* curr;
Node* temp;

• These are just variables and pointers
• They do not grow with input size
• No arrays, maps, or extra lists are used

What we are NOT using

• No extra linked list
• No hash map
• No array

So memory usage stays constant, no matter how big the linked list is.

Therefore, Space Complexity = O(1)

Final Summary (Perfect for Notes)

Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(1)

Tips for Beginners

• Use two loops to make your logic clear.
• Always check from the next node, not from the head again.
• Use visual examples to understand how curr and temp work.

Frequently Asked Questions (FAQ)

1. What is a duplicate in a linked list?

A duplicate is a node whose value appears more than once in a linked list. For example, in the list 1 → 2 → 2 → 3, the value 2 is a duplicate because it appears twice.

2. Why do we use Node* temp = curr->next?

This line ensures that we start checking for duplicates from the node after the current one (curr). It avoids re-checking nodes and makes counting accurate.

3. Can we count duplicates in a sorted linked list faster?

Yes! In a sorted linked list, duplicates are always next to each other. So, we can use a single loop to compare each node with the next, which reduces time complexity from O(n²) to O(n).

4. What is the time complexity of this method?

The beginner-friendly method using two nested loops has O(n²) time complexity, where n is the number of nodes in the list.

5. Can we count duplicates without using extra space?

Yes, the method shown in this guide uses O(1) extra space, meaning no additional memory is required apart from the linked list itself.

6. How is this different from using a hash map?

Using a hash map can reduce the time complexity to O(n), but it uses extra memory to store counts. The method in this guide is memory-efficient and easier for beginners to understand.

7. Can this method handle strings or other data types?

Yes, as long as the linked list stores comparable data (like integers, characters, or strings), you can modify the comparison curr->data == temp->data accordingly.

Read More : Master Most Asked Stack Coding Questions in Interviews