# Union intersection Two Linked Lists Using Merge Sort ### Introduction

Linked list is one of the most important concepts and data structures to learn while preparing for coding interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

According to the problem statement, we are given two singly linked lists, and our task is to find union and Intersection lists of both the given linked lists.

#### Input:

List1: 5→19→10→22→132
List2: 10→11→19→22→6

#### Output:

Intersection List: 10→19→22
Union List: 5→6→10→11→19→22→132

Intersection List contains all the nodes that are common in both the linked list.

Union List contains all the nodes that are present in both the given linked list.

If you are not aware of how to sort a linked list using merge sort, check out this article Merge sort on a singly-linked list.

### Algorithm for Intersection

1) First, apply merge sort on both the linked lists.
2) Now, Both the lists are sorted.
3) Now, traverse through both the linked lists simultaneously and create an Intersection list for those nodes that are common in both the linked lists.

### Dry Run   ### Code Implementation

```#include
using namespace std;

class Node{
public:
int data;
Node* next;

Node(int data){
this->data = data;
this->next = NULL;
}
};

/* find and return middle node of the linked list*/
Node* middle(Node* head, Node* tail) {

while(fast!=tail && fast->next!=tail){
slow = slow->next;
fast = fast->next->next;
}
Node* afterMiddle = slow->next;
slow->next = NULL;
return afterMiddle;
}

/* merge sort*/
}

while(tail->next){
tail = tail->next;
}

Node* part2 = mergeSort(afterMiddle);

Node *curr1 = part1, *curr2 = part2;

Node *si = NULL, *ei = NULL;

while(curr1 && curr2){
if(curr1->data <= curr2->data){
if(si == NULL){
si = curr1;
ei = curr1;
}else{
ei->next = curr1;
ei = curr1;
}
curr1 = curr1->next;
}else{
if(si == NULL){
si = curr2;
ei = curr2;
}else{
ei->next = curr2;
ei = curr2;
}
curr2 = curr2->next;
}
}

while(curr1){
ei->next = curr1;
ei = curr1;
curr1 = curr1->next;
}

while(curr2){
ei->next = curr2;
ei = curr2;
curr2 = curr2->next;
}

return si;
}

/* function to print the list */
cout<data<<" ";
}
cout<data == list2->data){
if(intersectionHead == NULL && intersectionTail == NULL){
intersectionTail = list1;
}else{
intersectionTail->next = list1;
intersectionTail = list1;
}
list1 = list1->next;
list2 = list2->next;
}else if(list1->data < list2->data){
list1 = list1->next;
}else if(list1->data > list2->data){
list2 = list2->next;
}
}

intersectionTail->next = NULL;
}

/* function to insert a node at the beginning of a linked list*/

Node* new_node = new Node(new_data);

/* link the old list with the new node */

/* move the head to point to the new node */

}

int main()
{

Node* list_intersection = NULL;

/*create a new linked lits 10->15->4->20 */

/*create a new linked lits 8->4->2->10 */

cout << "First list " << endl;
cout << "Second list " << endl;

cout << "Intersection list " << endl;
printList(list_intersection);
return 0;
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):

new_node = Node(new_data)

while fast != tail and fast.next != tail:
slow = slow.next
fast = fast.next.next

afterMiddle = slow.next
slow.next = None
return afterMiddle

while tail.next:
tail = tail.next

part2 = mergeSort(afterMiddle)

curr1 = part1
curr2 = part2

si, ei = None, None

while curr1 and curr2:
if curr1.data <= curr2.data:
if si == None:
si = curr1
ei = curr1
else:
ei.next = curr1
ei = curr1
curr1 = curr1.next
else:
if si == None:
si = curr2
ei = curr2
else:
ei.next = curr2
ei = curr2
curr2 = curr2.next

while curr1:
ei.next = curr1
ei = curr1
curr1 = curr1.next

while curr2:
ei.next = curr2
ei = curr2
curr2 = curr2.next

return si

while t1 and t2:
if t1.data < t2.data:
t1 = t1.next
elif t1.data > t2.data:
t2 = t2.next
else:
result.push(t2.data)
t1 = t1.next
t2 = t2.next

print("First list")
print("\nSecond list")

print("\nIntersection list")
printList(list_intersection)

```

#### Output

First list
10 15 4 20
Second list
8 4 2 10
Intersection list
4 10

Time Complexity: O(mLogm + nLogn). Since We have applied merge sort on both the linked list.
Space Complexity: O(n + m). Since We have applied merge sort on both the linked list.

### Algorithm for Union

1) First, apply merge sort on both the linked lists.
2) Now, Both the lists are sorted.
3) Now, traverse through both the linked lists simultaneously and create a Union List, which contains all the nodes present in both the linked lists.

### Dry Run   ### Code Implementation

```#include<bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node* next;

Node(int data){
this->data = data;
this->next = NULL;
}
};

/* find and return middle node of the linked list*/
Node* middle(Node* head, Node* tail) {

while(fast!=tail && fast->next!=tail){
slow = slow->next;
fast = fast->next->next;
}
Node* afterMiddle = slow->next;
slow->next = NULL;
return afterMiddle;
}

/* merge sort*/
}

while(tail->next){
tail = tail->next;
}

Node* part2 = mergeSort(afterMiddle);

Node *curr1 = part1, *curr2 = part2;

Node *si = NULL, *ei = NULL;

while(curr1 && curr2){
if(curr1->data <= curr2->data){
if(si == NULL){
si = curr1;
ei = curr1;
}else{
ei->next = curr1;
ei = curr1;
}
curr1 = curr1->next;
}else{
if(si == NULL){
si = curr2;
ei = curr2;
}else{
ei->next = curr2;
ei = curr2;
}
curr2 = curr2->next;
}
}

while(curr1){
ei->next = curr1;
ei = curr1;
curr1 = curr1->next;
}

while(curr2){
ei->next = curr2;
ei = curr2;
curr2 = curr2->next;
}

return si;
}

/* print function to print the linked list */
}
cout<<endl;
}

/* Function to find UNION LIST of two linked lists */
Node* unionList(Node* list1, Node* list2){
// If both linked list is empty then return NULL
if(list1 == NULL && list2==NULL){
return NULL;
}

if(list1 != NULL && list2 == NULL){
return list1;
}

if(list2 != NULL && list1 == NULL){
return list2;
}

Node* uniTail = NULL;

while(list1 && list2){
if(list1->data == list2->data){
if(uniHead == NULL && uniTail == NULL){
uniTail = list1;
}else{
uniTail->next = list1;
uniTail = list1;
}
list1 = list1->next;
list2 = list2->next;

}else if(list2->data < list1->data){
if(uniHead == NULL && uniTail == NULL){
uniTail = list2;
}else{
uniTail->next = list2;
uniTail = list2;
}

list2 = list2->next;
}else if(list2->data > list1->data){
if(uniHead == NULL && uniTail == NULL){
uniTail = list1;
}else{
uniTail->next = list1;
uniTail = list1;
}

list1 = list1->next;
}
}

}

/* function to insert a node at the beginning of a linked list*/

Node* new_node = new Node(new_data);

/* link the old list with the new node */

/* move the head to point to the new node */

}

int main()
{
Node* list_union = NULL;

/*create a new linked lits 10->15->4->20 */

/*create a new linked lits 8->4->2->10 */

cout << "First list " << endl;
cout << "Second list " << endl;

cout << "Union List " << endl;
printList(list_union);

return 0;
}
```

#### Output

First list
10 15 4 20
Second list
8 4 2 10
Union List
2 4 8 10 15 20

Time Complexity: O(mLogm + nLogn). Since We have applied merge sort on both the linked list.
Space Complexity: O(n + m). Since We have applied merge sort on both the linked list.

So, In this blog, we have learned How to find the Union and Intersection of two linked lists using Merge Sort. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.