## Algorithm

- Using merge sort, firstly Sort both Linked Lists
- Begin traversing both lists to get the union and intersection.
- Perform a merge operation on both linked lists while maintaining a pointer that links to the first node of both lists.
- Traverse and compare both the list till pointers are not null. If the pointer values are equal, add them to the intersection list and union list and move to the next node of both pointers; otherwise, if they are not equal, insert the smaller pointer value into the union list, and move to the next node.
- If you find one of the pointers is null, the other list and all of its nodes are traversed to the union list.

### Implementation

```
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ph push
/*structure of Link list node */
struct Node {
int data;
struct Node* next;
};
// insert a node to the start of a linked list
void push(struct Node** head, int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = (*head);
(*head) = newNode;
}
// here, we are using the two pointer approach
void Split(struct Node* head,struct Node** front, struct Node** back)
{
struct Node* fast, * slow;
if (head == NULL || head->next == NULL) {
*front = head;
*back = NULL;
}
else {
slow = head;
fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*front = head;
*back = slow->next;
slow->next = NULL;
}
}
struct Node* SortedMergelist(struct Node* l1,struct Node* l2)
{
struct Node* result = NULL;
if (l1 == NULL)
return (l2);
else if (l2 == NULL)
return (l1);
//Pick either l1 or l2, and recur
if (l1->data <= l2->data) {
result = l1;
result->next = SortedMergelist(l1->next, l2);
}
else {
result = l2;
result->next = SortedMergelist(l1, l2->next);
}
return (result);
}
// sorts the linked list by changing next pointers
void mergeSort(struct Node** headRef)
{
struct Node* head = *headRef,*a, *b;
if ((head == NULL) || (head->next == NULL))
return;
Split(head, &a, &b);
mergeSort(&a);
mergeSort(&b);
*headRef = SortedMergelist(a, b);
}
//Function to get union
struct Node* getUnion(struct Node* l1,struct Node* l2)
{
struct Node* result = NULL,*t1 = l1, *t2 = l2;
// Traverse both lists
while (t1 != NULL && t2 != NULL) {
if (t1->data < t2->data) {
push(&result, t1->data);
t1 = t1->next;
}
else if (t1->data > t2->data) {
push(&result, t2->data);
t2 = t2->next;
}
else {
push(&result, t2->data);
t1 = t1->next;
t2 = t2->next;
}
}
// Print all remaining elements of the lists
while (t1 != NULL) {
push(&result, t1->data);
t1 = t1->next;
}
while (t2 != NULL) {
push(&result, t2->data);
t2 = t2->next;
}
return result;
}
//Function to get intersection
struct Node* getIntersection(struct Node* l1,struct Node* l2)
{
struct Node* result = NULL, *t1 = l1, *t2 = l2;
// Traverse both lists
while (t1 != NULL && t2 != NULL) {
if (t1->data < t2->data)
t1 = t1->next;
else if (t1->data > t2->data)
t2 = t2->next;
else {
// Store current element in the list
push(&result, t2->data);
t1 = t1->next;
t2 = t2->next;
}
}
return result;
}
void print(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* list1 = NULL, * list2 = NULL;
struct Node* intersectionlist = NULL, * unionlist = NULL;
//creating linked list 12->5->14->20
ph(&list1, 12);
ph(&list1, 5);
ph(&list1, 14);
ph(&list1, 20);
//creating linked list 10->14->2->12
ph(&list2, 10);
ph(&list2, 14);
ph(&list2, 2);
ph(&list2, 12);
// Sorting the Linked List
mergeSort(&list1);
mergeSort(&list2);
intersectionlist = getIntersection(list1, list2);
unionlist = getUnion(list1, list2);
cout<<"First list: "<<endl;
print(list1);
cout<<"\nSecond list: "<<endl;
print(list2);
cout<<"\nIntersection list: "<<endl;
print(intersectionlist);
cout<<"\nUnion list: "<<endl;
print(unionlist);
return 0;
}
```

**Output**

#### Time Complexity

The time complexity of the above approach is O(m log m + n log n), where n and m are, respectively, the number of nodes in the linked lists.

#### Space Complexity

The space complexity of the above approach is O(m+n), where n and m are, respectively, the number of nodes in the linked lists.

Read More - __Time Complexity of Sorting Algorithms__

## Frequently Asked Questions

**What are the other methods of finding the Union and Intersection of two linked lists?**

We can find the union and intersection of two linked lists by brute force by searching for every element in two lists or using hashing.

**Which sorting algorithm is best for sorting a linked list?**

When sorting a linked list, merge sort is frequently used. Because of a linked list's slow random-access speed, some algorithms (quicksort) perform badly, while others (heapsort) are impossible.

**What is the complexity of merge sort?**

MergeSort's time complexity is O(n*Log n) in all three scenarios (worst, average and best).

**What is the Time Complexity of hashing approach for Union and Intersection?**

The time complexity of hashing approach is O(m+n) where m, n are the sizes of the linked lists.

## Conclusion

This article extensively discussed the problem of finding the Union and Intersection of two Linked Lists using merge sort and its time and space complexities.

We hope this blog has helped you enhance your knowledge regarding Linked Lists. After reading about the Union and Intersection of two Linked Lists using merge sort, are you not feeling excited to read more articles on this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and Analysis, Sorting Based Problems, Number Theory, and Dynamic Programing to learn.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

**Happy Learning!**