Using hashing remove duplicates from unsorted list
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct node{
int data; struct node* next;
};
struct node *newnode(int data)
{
struct node *temp= new node;
temp->data= data; temp->next= NULL; return temp;
} //nn ends
void remdup(struct node* head)
{
unordered_set<int> seen; //hash to store seen values
//name of hash is seen
//pick elements 1 by 1
struct node *curr= head;
struct node *prev= NULL;
while(curr!=NULL) //traverse the list to the last node
{
//if current data is seen before
if(seen.find(curr->data)!=seen.end())
{
prev->next=curr->next; delete(curr);
} //if ends
else {
seen.insert(curr->data); prev= curr;
} //else ends
curr= prev->next;
} //w ends
} //fends
void printlist(struct node* head)
{
while(head!=NULL)
{
cout<< head->data<<" "; head= head->next;
} //while ends
} // f ends
int main() {
struct node* head= newnode(10);
head->next = newnode(12);
head->next->next = newnode(11);
head->next->next->next = newnode(11);
head->next->next->next->next = newnode(12);
head->next->next->next->next->next =
newnode(11);
head->next->next->next->next->next->next =
newnode(10);
printlist(head);
remdup(head);
printlist(head);
return 0;
}
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home