Union and Intersection of Two Linked Lists (Using Hashing)

 Union( List1, List2) --> Create an empty Hash Table, Traverse both lists one by one, for each element visited, look for the element in the hash table, if not present --> add it, if present --> ignore it. 

Intersection( List1 , List 2 ) --> Create empty Hash Table, Traverse list 1, Initialize Result List as NULL, insert elements of List 1 in hash table, Traverse List2 and look for the element in the hash table, if present, Insert it into the Result List, else ignore it. 

Code-->

#include<bits/stdc++.h>

using namespace std;

struct Node{

    int data;

    struct Node* next;

};

//utility function to insert node 

void push(struct Node* head, int new_data)

{

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    new_node->data= new_data;

    new_node->next= head;

    head= new_node;

}

//function to store elements of both lists

void store(struct Node* head1, struct Node* head2, unordered_map<int, int>& st)

{

    struct Node* ptr1 = head1;

    struct Node* ptr2 = head2;


    //traverse both lists

    while(ptr1 != NULL || ptr2 !=NULL)

    {

        if(ptr1 !=NULL)

                st[ptr1->data]++;

                ptr1= ptr1->next;

        if(ptr2 !=NULL)

                st[ptr2-> data]++;

                ptr2= ptr2->next;

        }

}

//function to get Union of two linked lists

struct Node* union(unordered_map<int, int> st)

{

    struct Node* result = NULL;

    //push all elements into the resultant list

    for(auto i = st.begin(); i! = st.end(); i++ )

        push(&result, i->first);

    return result;

}

//function to get Intersection of two linked lists

struct Node* intersection(unordered_map<int, int> st)

{

    struct Node* result = NULL;

    //push element having occurrence of 2 (list 1 and list 2)

    for( auto i = st.begin(); i!= st.end(); i++)

        if(i->second ==2 )

            push(&result, i->first);

    return result;

}




    



Popular posts from this blog

Finding the Subarrays (Hackerearth)

Palindrome Index (Hackerrank)

Sherlock and Array (Hackerrank)