Program to delete duplicates from a linked list

Program to delete duplicates from a linked list

Given a list , write a Program to delete duplicates from a linked list

Sample input:-

11->12->11->13->12

Sample output:-

11->12->13

Program to delete duplicates from a linked list:-

The objective of the code is to delete all the duplicates from the list . For that we will  use two methods .

 

Method 1 (Using loop) :-

In this method we will use two loops for deleting the duplicate values . the time complexity of this method is O(n²) . and space complexity is O(1).

Code (C++):-

#include<bits/stdc++.h>
using namespace std;

// structure of node
struct node
{
    int data;
    struct node* next;
};

struct node *head=NULL;

// fucntion to create a new node 
struct node * CreateNode(int d)
{
    struct node *temp;
    temp=new node;
    temp->next=NULL;
    temp->data=d;
    return temp;
}

// function for inserting new element 
void insert(int d)
{
    node *temp,*t;
    temp=CreateNode(d);
    if(head==NULL)
     head=temp;
    else
    {
       t=head;
       while(t->next!=0)
         t=t->next;
       t->next=temp;
    }
}


// function for removing duplicates 
void removeduplicate()
{
    struct node * curr, *pre,*t;
    t=head;
    while(t->next!=NULL )
    {
        curr=t->next;
        pre=NULL;
        while(curr!=NULL)
        {
            // if duplicates present then delete it
            if(t->data == curr->data)
            {
                pre->next=curr->next;
                free(curr);
            }
            else
            {
                pre=curr;
            }
            curr=pre->next;
            
        }
        t=t->next;
    }
}

// function for print the element of the list 
void printlist()
{
    struct node *t;
    t=head;
    while(t!=NULL)
    {
        cout<<t->data<<" ";
        t=t->next;
    }
    cout<<endl;
}

// Driver function
int main()
{
    int n,ele;
    cout<<"Enter the number of nodes in the list"<<endl;
    cin>>n;
    cout<<"Enter "<<n<<" elements"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>ele;
        insert(ele);
    }
    
    cout<<"Original list"<<endl;
    printlist();
    
    // delete duplicates
    removeduplicate();
    cout<<"List after deleting the duplicates"<<endl;
    printlist();
    return 0;
}

 

Output:-

Enter the number of nodes in the list
5
Enter 5 elements
11 12 11 13 12
Original list
11 12 11 13 12 
List after deleting the duplicates
11 12 13

 

Time Complexity:-  O(n²)

Space complexity :- O(1)

Method 2 (BY using hashing ):-

In this method we will use hashing . we take a set (You can use any data structure ) first we check is element present in set or not . if yes then we don’t this again so we delete this node . and if no then insert it into set  and update pointers . Time complexity for this method is O(n) and the space complexity is O(n) extra space for set.

#include<bits/stdc++.h>
using namespace std;

// structure of node
struct node
{
    int data;
    struct node* next;
};

struct node *head=NULL;

// fucntion to create a new node 
struct node * CreateNode(int d)
{
    struct node *temp;
    temp=new node;
    temp->next=NULL;
    temp->data=d;
    return temp;
}

// function for inserting new element 
void insert(int d)
{
    node *temp,*t;
    temp=CreateNode(d);
    if(head==NULL)
     head=temp;
    else
    {
       t=head;
       while(t->next!=0)
         t=t->next;
       t->next=temp;
    }
}


// function for removing duplicates 
void removeduplicate()
{
    unordered_set<int> s;
    struct node *curr,*pre;
    curr=head;
    while(curr!=NULL)
    {
        // if curr data is in set 
        if(s.find(curr->data)!=s.end())
        {
            pre->next=curr->next;
            delete (curr);
        }
        else
        {
           s.insert(curr->data);
           pre=curr;
           
        }
        
        curr=pre->next;
    }
}

// function for print the element of the list 
void printlist()
{
    struct node *t;
    t=head;
    while(t!=NULL)
    {
        cout<<t->data<<" ";
        t=t->next;
    }
    cout<<endl;
}

// Driver function
int main()
{
    int n,ele;
    cout<<"Enter the number of nodes in the list"<<endl;
    cin>>n;
    cout<<"Enter "<<n<<" elements"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>ele;
        insert(ele);
    }
    
    cout<<"Original list"<<endl;
    printlist();
    
    // delete duplicates
    removeduplicate();
    cout<<"List after deleting the duplicates"<<endl;
    printlist();
    return 0;
}

Output:-

Enter the number of nodes in the list
5
Enter 5 elements
11 12 11 13 12
Original list
11 12 11 13 12 
List after deleting the duplicates
11 12 13

 

Time Complexity:-  O(n)

Space complexity :- O(n)

Recommended Post:-