Table of contents
1.
Introduction
2.
Naive Approach 
2.1.
Algorithm
2.2.
Implementation in C++
2.3.
C++
2.4.
Complexity Analysis
2.5.
Recursive Implementation of Naive Approach
2.6.
C++
2.7.
Complexity Analysis
3.
Using Two Pointers Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.3.
C++
3.4.
Complexity Analysis
4.
Using Maps Approach
4.1.
Algorithm
4.2.
Implementation in C++
4.3.
C++
4.4.
Complexity Analysis
5.
Using Set data structure
5.1.
Algorithm
5.2.
Implementation in C++
5.3.
C++
5.4.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
What are the types of the linked list?
6.2.
How do you remove duplicates from a linked list?
6.3.
How to remove duplicate values in linked list in C?
6.4.
How do you remove duplicates from LinkedList in Java?
6.5.
How do I remove duplicates in doubly linked list?
7.
Conclusion
Last Updated: Apr 17, 2024
Medium

Remove Duplicates from Linked List

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Remove Duplicates from Linked List

In this blog, we will learn how we can remove duplicates from linked list. So let's suppose we have a Linked List sorted in increasing order, and it may or may not contain some duplicate nodes. Now we need to remove all the duplicate nodes from this link list. For example-

remove duplicates from linked list

There are numerous approaches to doing the above task, as we can travel through the linked list by comparing the current node with its next node and removing the next node if it is equal. Or we can also use a two-pointer approach where the first pointer helps us traverse through the linked list, and the second pointer only points to the distinct nodes in the list. Another approach could be to use an unordered map to store all the nodes, and as maps don't allow duplicates, thus we will get rid of all the duplicates. So let's see all of these methods one by one; start with the simple traversal-based approach.

Recommended: Before stepping on to the solution, try it by yourself on Coding Ninjas Studio.

Here are the list of approaches to remove duplicates from linked list are as follows:

  • Naive Approach
  • Using Two Pointers Approach
  • Using Maps Approach
  • Using Set data structure

Naive Approach 

The naive approach to solve this problem is to iterate through the linked list and keep comparing the current node with its next node, and if they are the same, delete the next node and move to the next node. Finally, print the linked list. This approach can be implemented using recursion, so let's go through both implementations one by one.

Algorithm

  1. Take the linked list from user input-
  2. Iterate through the linked list and compare the current node with the next node-
  3. If they are equal, delete the next node after storing the pointer to the next node of the next node. Then link the current node with the next to the next node.
  4. If not, then continue traversing the linked list.
  5. Finally, print the linked list.

Implementation in C++

  • C++

C++

#include <bits/stdc++.h>
using namespace std;
//Structure for a node in the linked list.
struct node
{
   int data;
   struct node *next;
};
//Function to remove duplicates.
void removeduplicates(node* head)
{
   //Pointer to traverse the linked list.
   node* curr=head;
   //pointer to store the next to the next pointer of the current
   //node.
   node* nextofcurr;
   //For empty linked list.
   if(curr==nullptr)
   {
       return;
   }
   //Traversing through the linked list.
   while(curr->next!=nullptr)
   {
       //When the next node is a duplicate of the current node.
       if(curr->data==curr->next->data)
       {
           //Store the next of the next node.
           nextofcurr=curr->next->next;
           //Delete the next node
           free(curr->next);
           //Assign the next node to the iterator.
           curr->next=nextofcurr;
       }
       //When the next node is not a duplicate of the current
       //node.
       else
       {
           curr=curr->next;
       }
   }
}
//Function to push nodes into the list.
void push(struct node** headr, int new_val)
{
   //Creatng a new node.
   struct node* new_node= new node();
   //Putting the value in the node.
   new_node->data= new_val;
   //Linking the node to the list.
   new_node->next=(*headr);
   //Shifting the head pointer to the new node.
   *headr= new_node;
}
//Driver function.
int main()
{
   //Creating an empty list.
   struct node* head=nullptr;
   //Enter no  of nodes in the node.
   int size;
   cout<<"Enter the number of nodes in the list- ";
   cin>>size;
   //Pushing the nodes in it.
   cout<<"Enter the nodes in the list- ";
   for(int i=0;i<size;i++)
   {
       int a;
       cin>>a;
       push(&head,a);
   }
   //To remove duplicates from the sorted linked list.
   removeduplicates(head);
   //Printing the linked list.   
   while(head!=nullptr)
   {
       cout<<head->data<<" ";
       head=head->next;
   }
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

7
5 4 3 2 2 2 1

Output

Enter the number of nodes in the list- 
Enter the nodes in the list-
1 2 3 4 5 

Complexity Analysis

The time complexity of this approach is- O(N), where N is the number of nodes in the linked list.

The space complexity of this approach is- O(1)

Recursive Implementation of Naive Approach

  • C++

C++

#include <bits/stdc++.h>
using namespace std;
//Structure for a node in linked list.
struct node
{
   int data;
   struct node *next;
};
//Function to remove duplicates.
void removeduplicates(node* head)
{
   //To store the duplicate nodes which will be deleted.
   node* todelete;
   //For empty linked list.
   if(head==nullptr)
   {
       return;
   }
   //Traversing through the linked list.
   if(head->next!=nullptr)
   {
       //When the next node is a duplicate of the current node.
       if(head->data==head->next->data)
       {
           //For removing the duplicate node.
           todelete=head->next;
           //Moving the current node to the next to the next node.
           head->next=head->next->next;
           //Delete the duplicate node
           free(todelete);
           //Recursive call to the fucntion with the next node.
           removeduplicates(head);
       }
       else
       {
           //When the next node is not a duplicate of the
           //current node.
           removeduplicates(head->next);
       }
   }
}
//Function to push nodes into the list.
void push(struct node** headr, int new_val)
{
   //Creatng a new node.
   struct node* new_node= new node();
   //Putting the value in the node.
   new_node->data= new_val;
   //Linking the node to the list.
   new_node->next=(*headr);
   //Shifting the head pointer to the new node.
   *headr= new_node;
}
//Driver function.
int main()
{
   //Creating an empty list.
   struct node* head=nullptr;
   //Enter no  of nodes in the node.
   int size;
   cout<<"Enter the number of nodes in the list- ";
   cin>>size;
   //Pushing the nodes in it.
   cout<<"Enter the nodes in the list- ";
   for(int i=0;i<size;i++)
   {
       int a;
       cin>>a;
       push(&head,a);
   }
   //To remove duplicates from the sorted linked list.
   removeduplicates(head);
   //Printing the linked list.   
   while(head!=nullptr)
   {
       cout<<head->data<<" ";
       head=head->next;
   }
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

7
5 4 3 2 2 2 1

Output

Enter the number of nodes in the list- 
Enter the nodes in the list-
1 2 3 4 5 

Complexity Analysis

The time complexity of this approach is- O(N)

The space complexity of this approach is- O(N)

Using Two Pointers Approach

This approach uses two-pointers to remove duplicates from the sorted linked list. The first pointer iterates through the whole list. And the second pointer moves over only those nodes which are distinct. While iterating through the list, whenever the first pointer encounter duplicate nodes, it skips them, and when it encounters a distinct node, it moves the second pointer from the last distinct node to this new node.

Algorithm

  1. Take the linked list from user input-
  2. Declare two-pointers and initialize them with the head of the linked list
  3. Iterate through the list using the first pointer-
  4. If it encounters a node that duplicates its previous, it does nothing, and if the node is distinct, it moves the second pointer to that node.
  5. Print the linked list.

Implementation in C++

  • C++

C++

#include <bits/stdc++.h>
using namespace std;
//Structure for a node in linked list.
struct node
{
   int data;
   struct node *next;
};
//Function to remove duplicates.
void removeduplicates(node* head)
{
   //Two reference pointers, one for iterating through the linked
   //list, another for pointing to first occurence of every
   //distinct node.
   node *ptr1 =head;
   node *ptr2=head;
   //Traversing through the list.
   while(ptr1!=nullptr)
   {
       //Comparing the current node with the next node.
       if(ptr1->data!=ptr2->data)
       {
           //If a new node is found, skip the duplicates.
           ptr2->next=ptr1;
           ptr2=ptr1;
       }
       //Move the iterator to the next node.
       ptr1=ptr1->next;
   }
   //When the last node has duplicates.
   if(ptr2!=ptr1)
   {
       ptr2->next=nullptr;
   }
}
//Function to push nodes into the list.
void push(struct node** headr, int new_val)
{
   //Creatng a new node.
   struct node* new_node= new node();
   //Putting the value in the node.
   new_node->data= new_val;
   //Linking the node to the list.
   new_node->next=(*headr);
   //Shifting the head pointer to the new node.
   *headr= new_node;
}
//Driver function.
int main()
{
   //Creating an empty list.
   struct node* head=nullptr;
   //Enter no  of nodes in the node.
   int size;
   cout<<"Enter the number of nodes in the list- ";
   cin>>size;
   //Pushing the nodes in it.
   cout<<"Enter the nodes in the list- ";
   for(int i=0;i<size;i++)
   {
       int a;
       cin>>a;
       push(&head,a);
   }
   //To remove duplicates from the sorted linked list.
   removeduplicates(head);
   //Printing the linked list.   
   while(head!=nullptr)
   {
       cout<<head->data<<" ";
       head=head->next;
   }
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

7
5 4 3 2 2 2 1

Output

Enter the number of nodes in the list- 
Enter the nodes in the list-
1 2 3 4 5 

Complexity Analysis

The time complexity of this approach is- O(N)

The space complexity of this approach is- O(1)

Using Maps Approach

Another approach to solving this problem is using maps. We traverse through the linked list and check if the node has already occurred or node. If it has not occurred, we print it and mark it as visited on the map. And skip it if it is already visited.

Algorithm

  1. Take the linked list from user input-
  2. Create a map that takes node data and boolean variables as key-value pairs.
  3. Traverse through the linked list, and if a node appears for the first time or not-
  4. If Yes, print it and mark it as visited on the map.
  5. Else move on to the next node.

Implementation in C++

  • C++

C++

#include <bits/stdc++.h>
using namespace std;
//Structure for a node in the linked list.
struct node
{
   int data;
   struct node *next;
};
//Function to remove duplicates.
void removeduplicates(node* head)
{
   //Map to store the distinct values.
   unordered_map<int, bool> distinctnodes;
   //To traverse through the nodes.
   node* curr=head;
   while(curr)
   {
       //If the current nodes is its first occurence.
       if(distinctnodes.find(curr->data)==distinctnodes.end())
       {
           cout<<curr->data<<" ";
       }
       //Marked the node as visited.
       distinctnodes[curr->data]=true;
       curr=curr->next;
   }
}
//Function to push nodes into the list.
void push(struct node** headr, int new_val)
{
   //Creatng a new node.
   struct node* new_node= new node();
   //Putting the value in the node.
   new_node->data= new_val;
   //Linking the node to the list.
   new_node->next=(*headr);
   //Shifting the head pointer to the new node.
   *headr= new_node;
}
//Driver function.
int main()
{
   //Creating an empty list.
   struct node* head=nullptr;
   //Enter no  of nodes in the node.
   int size;
   cout<<"Enter the number of nodes in the list- ";
   cin>>size;
   //Pushing the nodes in it.
   cout<<"Enter the nodes in the list- ";
   for(int i=0;i<size;i++)
   {
       int a;
       cin>>a;
       push(&head,a);
   }
   //To remove duplicates from the sorted linked list.
   removeduplicates(head);
}
You can also try this code with Online C++ Compiler
Run Code

Input

7
5 4 3 2 2 2 1

Output

Enter the number of nodes in the list- 
Enter the nodes in the list-
1 2 3 4 5 

Complexity Analysis

The time complexity of this approach is- O(N)

The space complexity of this approach is- O(1)

Using Set data structure

Using a set data structure is an efficient approach for removing duplicates from a linked list. Sets in C++ (and similarly in other languages) provide constant time complexity for insertion and lookup operations, making them ideal for this task. By iterating through the linked list and maintaining a set of unique values encountered so far, we can easily identify and remove duplicates.

Algorithm

  1. Traverse the linked list.
  2. For each node, check if its value already exists in the set.
  3. If it does not exist, add its value to the set and continue to the next node.
  4. If it does exist, remove the node from the linked list.
  5. Continue until the end of the linked list is reached.

Implementation in C++

  • C++

C++

#include <iostream>
#include <unordered_set>

using namespace std;

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* removeDuplicates(ListNode* head) {
if (!head) return nullptr;

unordered_set<int> seen;
ListNode *current = head;
ListNode *prev = nullptr;

while (current) {
if (seen.find(current->val) == seen.end()) {
seen.insert(current->val);
prev = current;
} else {
prev->next = current->next;
delete current;
}
current = prev->next;
}

return head;
}

void printList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}

int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(4);

cout << "Original List: ";
printList(head);

head = removeDuplicates(head);

cout << "List after removing duplicates: ";
printList(head);

return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output

Original List: 1 2 3 2 4 
List after removing duplicates: 1 2 3 4 

Complexity Analysis

  • Time complexity: O(n), where n is the number of nodes in the linked list. This is because we traverse the entire linked list once.
  • Space complexity: O(n), where n is the number of unique elements in the linked list. This is because we store unique elements in a set.

Frequently Asked Questions

What are the types of the linked list?

The linked list is generally of four types-   
- Singly-linked list 
- Doubly linked list
- Circular linked list
- Doubly circular linked list 

How do you remove duplicates from a linked list?

Duplicates can be removed by using two pointers approach. The first pointer iterates through the whole list. And the second pointer moves over only those nodes which are distinct. While iterating through the list, whenever the first pointer encounter duplicate nodes, it skips them. 

How to remove duplicate values in linked list in C?

Duplicates can be removed by a naive approach. The naive approach is to iterate through the linked list and keep comparing the current node with its next node, and if they are the same, delete the next node and move to the next node. 

How do you remove duplicates from LinkedList in Java?

A set does not have duplicate elements in the Collection structure. We will use LinkedHashSet because it will maintain the order in the same way as LinkedList does since we are aware of this. By transforming the linked list into a linked hash set, we will eliminate duplicates from it.

How do I remove duplicates in doubly linked list?

By utilising a basic technique, duplicates in a doubly linked list can be eliminated. Two loops are utilized in this manner, which is the simplest. The inner loop compares the selected element with the other elements after the outer loop picks each element one at a time.

Conclusion

In this blog, we learned the different approaches used to remove duplicates from the sorted linked list.

  • We started with the basic approach of traversing through the linked list and comparing the current node with the next node, and if they are equal, delete the next node and link the current node to the next node.
  • The second approach used two pointers. One iterates through the whole list, and the second pointer moves only over the distinct nodes. In this method, the first pointer continues traversing until it finds a distinct node, and then the second pointer is moved to that node. Finally, we print the nodes traversed by the second pointer.
  • The last approach uses a map to remove duplicates from the sorted linked list. We create a map with integer and bool as key-value pairs. Now we traverse through the linked list and check if a node is visited or not. If not, we print it, and if visited, we continue the traversal without printing. 
     

More suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

Refer to the top list of problems of Map data structure

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, and many more. 

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass