Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Algorithm
3.1.
Implementation
3.1.1.
Time Complexity
3.1.2.
Space Complexity
4.
4.1.
What are the other methods of finding the Union and Intersection of two linked lists?
4.2.
Which sorting algorithm is best for sorting a linked list?
4.3.
What is the complexity of merge sort?
4.4.
What is the Time Complexity of hashing approach for Union and Intersection?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Union and Intersection of two Linked Lists (using Merge Sort)

## Introduction

Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. There are various standard linked list problems and techniques. This blog tackles a coding task that involves finding the union and intersection of two Linked Lists using the merge sort.

Recommended Topic, Floyds Algorithm

## Problem Statement

Using the merge sort, we have to generate union and intersection lists that should include the union and intersection of the elements in the linked lists. The order of the elements in the union and intersection of two linked lists is not relevant.

### Sample Examples

Input

List 1:

List 2:

Output

Intersection:

Union:

Explanation

These two lists have 14 and 12 nodes in common. The union lists include all of the nodes from both lists.

## Algorithm

1. Using merge sort, firstly Sort both Linked Lists
2. Begin traversing both lists to get the union and intersection.
3. Perform a merge operation on both linked lists while maintaining a pointer that links to the first node of both lists.
4. 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.
5. 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;
}

// 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) {
*back = NULL;
}
else {

while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*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)
{

if ((head == NULL) || (head->next == NULL))
return;

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 AnalysisSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem 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!

Live masterclass