In this blog, we will learn how we can remove duplicates from a sorted 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-
Given linked list- 1 2 2 2 3 4 5
After removing duplicates from the sorted linked list- 1 2 3 4 5
|
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 CodeStudio.
Approach 1: Naive
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
- Take the linked list from user input-
- Iterate through the linked list and compare the current node with the next node-
- 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.
- If not, then continue traversing the linked list.
- Finally, print the linked list.
Implementation
#include
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;
coutsize;
//Pushing the nodes in it.
coutnext->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;
coutsize;
//Pushing the nodes in it.
coutnext=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;
coutsize;
//Pushing the nodes in it.
cout