Given two linked lists, create another two linked lists to get union and intersection of the elements of existing lists.
Table of Contents
Example
Input:
List1: 5 → 9 → 10 → 12 → 14
List2: 3 → 5 → 9 → 14 → 21
Output:
Intersection_list: 14 → 9 → 5
Union_list: 21 → 14 → 12 → 10 → 9 → 5 → 3
Explanation: A linked list is the collection of nodes. Every node is connected in sequence. We can get the intersection and union of two linked lists by using several methods. But, the efficient method to use in this case is first, sort both the linked list using merge sort and then linearly check both the sorted linked list to get intersection and union of both linked lists. Here, the merge sort is often preferred for sorting of the linked list than other algorithms that perform poorly.
Algorithm
- Create a linked list by declaring the head and next pointer of the list.
- Insert the elements in both the list using insert func.
- Sort both linked lists using the merge sort algorithm.
- Finally, linearly scan both the sorted list to get the union and intersection of the list.
Explanation
First, we create a node by creating a Node class in our program So, that we could create our Linked list. In our program, we create two unordered linked list. After that, we sort both the linked list by using our sorting algorithm and then we create our function to get the union and intersection of our linked lists. After sorting both the linked lists it easy to scan them linearly such that we could get union and intersection of our linked lists.
For instance, create two linked lists ‘list1’ and ‘list2’, and insert elements in both of them by our Node class in java or Node structure in c++. After that, we find the union of our both linked lists list1 and list2 by using the function that we made ‘get_union’ in which we take the head of both linked list as an argument in it and we create a temporary list to save the union element in it of both lists with the help of while loop first while loop to insert the element of the first list in temp. list and second to insert the list 2 elements in temp. list if they not already in the list and finally we got list filled with elements which are common in both linked list. After that, we will use our ‘get Intersection’ method to find the intersection of both linked lists, in which we again take the heads of both linked list and again we will use while loop in it to insert an element of both linked list only if they are common in both of linked list.
Implementation
C++ program for Union and Intersection of two Linked Lists
#include<iostream>
#include<stdlib.h>
using namespace std;
struct Node
{
int value;
struct Node* next;
};
void insert(struct Node** head, int new_value)
{
struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));
NewNode->value = new_value;
NewNode->next = (*head);
(*head) = NewNode;
}
void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
struct Node* fast;
struct Node* slow;
if (source==NULL || source->next==NULL)
{
*front = source;
*back = NULL;
}
else
{
slow = source;
fast = source->next;
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
*front = source;
*back = slow->next;
slow->next = NULL;
}
}
struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
struct Node* result = NULL;
if (fst == NULL)
return(sec);
else if (sec==NULL)
return(fst);
if (fst->value <= sec->value)
{
result = fst;
result->next = Sort_merge(fst->next, sec);
}
else
{
result = sec;
result->next = Sort_merge(fst, sec->next);
}
return(result);
}
void Sort(struct Node** head)
{
struct Node *head_node= *head;
struct Node *a, *b;
if ((head_node == NULL) || (head_node->next == NULL))
return;
Front_Back(head_node, &a, &b);
Sort(&a);
Sort(&b);
*head = Sort_merge(a, b);
}
struct Node *get_Union(struct Node *head1, struct Node *head2)
{
struct Node *result = NULL;
struct Node *t1 = head1, *t2 = head2;
while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
{
insert(&result, t1->value);
t1 = t1->next;
}
else if (t1->value>t2->value)
{
insert(&result, t2->value);
t2 = t2->next;
}
else
{
insert(&result, t2->value);
t1 = t1->next;
t2 = t2->next;
}
}
while (t1 != NULL)
{
insert(&result, t1->value);
t1 = t1->next;
}
while (t2 != NULL)
{
insert(&result, t2->value);
t2 = t2->next;
}
return result;
}
struct Node *get_Intersection(struct Node *head1, struct Node *head2)
{
struct Node *result = NULL;
struct Node *t1 = head1, *t2 = head2;
while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
t1 = t1->next;
else if (t1->value > t2->value)
t2 = t2->next;
else
{
insert(&result, t2->value);
t1 = t1->next;
t2 = t2->next;
}
}
return result;
}
void printList (struct Node *node)
{
while (node != NULL)
{
cout<<node->value << " ";
node = node->next;
}
cout<<endl;
}
int main()
{
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersection_list = NULL;
struct Node* union_list = NULL;
insert(&head1, 20);
insert(&head1, 4);
insert(&head1, 15);
insert(&head1, 10);
insert(&head1, 11);
insert(&head2, 10);
insert(&head2, 2);
insert(&head2, 4);
insert(&head2, 8);
Sort(&head1);
Sort(&head2);
intersection_list = get_Intersection(head1, head2);
union_list = get_Union(head1, head2);
cout<<"First list is \n";
printList(head1);
cout<<"\nSecond list is \n";
printList(head2);
cout<<"\nIntersection list is \n";
printList(intersection_list);
cout<<"\nUnion list is \n";
printList(union_list);
return 0;
}
First list is 4 10 11 15 20 Second list is 2 4 8 10 Intersection list is 10 4 Union list is 20 15 11 10 8 4 2
Java program for Union and Intersection of two Linked Lists
class Solution1
{
Node head;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void get_union(Node hd1, Node hd2)
{
Node t1 = hd1, t2 = hd2;
while (t1 != null)
{
insert(t1.data);
t1 = t1.next;
}
while (t2 != null)
{
if (!is_Present(head, t2.data))
insert(t2.data);
t2 = t2.next;
}
}
void get_intrSection(Node hd1, Node hd2)
{
Node rst = null;
Node t1 = hd1;
while (t1 != null)
{
if (is_Present(hd2, t1.data))
insert(t1.data);
t1 = t1.next;
}
}
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
void insert(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
boolean is_Present(Node head, int data)
{
Node t = head;
while (t != null)
{
if (t.data == data)
return true;
t = t.next;
}
return false;
}
public static void main(String args[])
{
Solution1 llist1 = new Solution1();
Solution1 llist2 = new Solution1();
Solution1 unin = new Solution1();
Solution1 intersecn = new Solution1();
llist1.insert(20);
llist1.insert(4);
llist1.insert(15);
llist1.insert(10);
llist2.insert(10);
llist2.insert(2);
llist2.insert(4);
llist2.insert(8);
intersecn.get_intrSection(llist1.head, llist2.head);
unin.get_union(llist1.head, llist2.head);
System.out.println("First List is");
llist1.printList();
System.out.println("Second List is");
llist2.printList();
System.out.println("Intersection List is");
intersecn.printList();
System.out.println("Union List is");
unin.printList();
}
}
First List is 10 15 4 20 Second List is 8 4 2 10 Intersection List is 4 10 Union List is 2 8 20 4 15 10
Complexity Analysis for Union and Intersection of two Linked Lists
Time Complexity
O(m+n) where “m” and “n” are the number of elements present in first and second lists respectively.
Space Complexity
O(m+n) where “m” and “n” are the number of elements present in first and second lists respectively.