Remove duplicate from a linked list in C++
In this tutorial, we will learn how to remove duplicate from a linked list in c++.
For example-
2 4 5 6 2 3 4
After removing duplicate elements:
2 4 5 6 3
How to remove duplicate from a linked list in C++
Method 1: by using STL
Here we will be using a set from STL. Sets are a type of container in which each element has to be unique. For example- if we are storing
2 3 4 2 3 1 in a set. Our set will actually be 1 2 3 4.
It is because it stores elements only once and that too in sorted order.
Algorithm
- Create a list.
- Insert the elements of a list in the set one by one.
- And then print the elements of the set. (set will not store the duplicate ones)
Here, is the code:
#include<bits/stdc++.h> using namespace std; int main() { list<int> mylist; int n; cin>>n; int data; for(int i=0;i<n;i++) { cin>>data; mylist.push_back(data); } set<int> set; for(list<int>::iterator head=mylist.begin();head!=mylist.end();head++) { set.insert(*head); } for(auto it=set.begin();it!=set.end();it++) { cout<<*it<<"-->"; } }
Method 2: By using two loops
- Pick elements one by one.
- Compare the element with the rest of the elements.
- If you find a duplicate element then delete it.
- Else increment the pointer.
- Do this till ptr1–>next==NULL.
- And for the inner loop, till ptr2->next==NULL.
Here, is the code:
#include<iostream> using namespace std; class node{ public: int data; node* next; node(int d) { data=d; next=NULL; } }; void printll(const node *head) { while(head!=NULL) { cout<<head->data<<" "; head=head->next; } cout<<endl; } node *createll(int n){ int x; node *head=NULL; node *tail=NULL; for(int i=0;i<n;i++) { cin>>x; node *n=new node(x); if(head==NULL) { head=n; tail=n; } else { tail->next=n; tail=tail->next; } } return head; } void removeDuplicates(node *start) { node *ptr1, *ptr2, *dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != NULL && ptr1->next != NULL) { ptr2 = ptr1; while (ptr2->next != NULL) { /* If duplicate then delete it */ if (ptr1->data == ptr2->next->data) { /* sequence of steps is important here */ dup = ptr2->next; ptr2->next = ptr2->next->next; delete(dup); } else /* This is tricky */ ptr2 = ptr2->next; } ptr1 = ptr1->next; } } int main() { int n; cin>>n; node *head=createll(n); removeDuplicates(head); printll(head); }
Input:
5 2 3 2 1 2
Output:
2 3 1
Also refer to:
Leave a Reply