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
- Take the linked list from user input-
- Create a map that takes node data and boolean variables as key-value pairs.
- Traverse through the linked list, and if a node appears for the first time or not-
- If Yes, print it and mark it as visited on the map.
- Else move on to the next node.
Implementation in 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
- Traverse the linked list.
- For each node, check if its value already exists in the set.
- If it does not exist, add its value to the set and continue to the next node.
- If it does exist, remove the node from the linked list.
- Continue until the end of the linked list is reached.
Implementation in 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!!