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;
}