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:-
- Primary test
- Sum or difference
- point and line
Wipro :-
- Update the booking ID | Wipro previous year question paper solution
- Pages in PDF
- Find the location id
- Find the odd digits
- Find the Product ID
Infytq :-
Key Points;-
Hackerrank:-
- Python : missing characters : hackerrank solution
- Python : string transformation | Hackerrank solution
- Active Traders certification test problem | Hackerrank Solution
- Usernames changes certification test problem | Hackerrank Solution
- string Representation of objects certification test hackerrank solution
- Average Function | hackerrank certification problem solution
C-tutorial:-
- Micros in C
- Pointer in c
- Function declaration
- Types of user define function
- return type of function
- 2D array
See more:-
- c program to convert specified days into years weeks and days
- Print Reverse Hollow Pyramid
- Update the booking ID | Wipro previous year question paper
- Pages in PDF | Wipro previous year question paper
- Sparse Matrix in data structure
- Find the location ID | Wipro previous year Coding question
- find the odd digits | Wipro Coding question
- Find the product id | Wipro Coding question
- Difference between static and dynamic memory allocation
- What is asymptotic Notation