Thursday, January 28, 2021

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