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

1. Create a list.
2. Insert the elements of a list in the set one by one.
3. 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

1. Pick elements one by one.
2. Compare the element with the rest of the elements.
3. If you find a duplicate element then delete it.
4. Else increment the pointer.
5. Do this till ptr1–>next==NULL.
6. 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:

Reverse a linked list using STL