Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

Union intersection Two Linked Lists Using Merge Sort

PrepBytes

Last Updated on March 10, 2022 by Ria Pathak

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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) {
Node* slow = head;
Node* fast = head;
while(fast!=tail && fast->next!=tail){
slow = slow->next;
fast = fast->next->next;
}
Node* afterMiddle = slow->next;
slow->next = NULL;
return afterMiddle;
}
/* merge sort*/
Node* mergeSort(Node* head){
if(head == NULL || head->next == NULL){
return head;
}
Node* tail = head;
while(tail->next){
tail = tail->next;
}
Node* afterMiddle = middle(head, tail);
Node* part1 = mergeSort(head);
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 */
void printList(Node* head){
while(head != NULL){
cout<<head->data<<" ";
head = head->next;
}
cout<<endl; }="" *="" function="" to="" find="" the="" intersection="" list="" node*="" intersectionlist(node*="" list1,="" list2){="" if(list1="=" null="" ||="" list2="=NULL){" return="" null;="" intersectionhead="NULL;" intersectiontail="NULL;" while(list1="" &&="" if(list1-="">data == list2->data){
if(intersectionHead == NULL && intersectionTail == NULL){
intersectionHead = list1;
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;
return intersectionHead;
}
/* function to insert a node at the beginning of a linked list*/
Node* push(Node* head, int new_data){
Node* new_node = new Node(new_data);
/* link the old list with the new node */
new_node->next = head;
/* move the head to point to the new node */
head = new_node;
return head;
}
int main()
{
/* Start with the empty list */
Node* head1 = NULL;
Node* head2 = NULL;
Node* list_intersection = NULL;
/*create a new linked lits 10->15->4->20 */
head1 = push(head1, 20);
head1 = push(head1, 4);
head1 = push(head1, 15);
head1 = push(head1, 10);
/*create a new linked lits 8->4->2->10 */
head2 = push(head2, 10);
head2 = push(head2, 2);
head2 = push(head2, 4);
head2 = push(head2, 8);
cout << "First list " << endl;
printList(head1);
cout << "Second list " << endl;
printList(head2);
head1 = mergeSort(head1);
head2 = mergeSort(head2);
list_intersection = intersectionList(head1, head2);
cout << "Intersection list " << endl;
printList(list_intersection);
return 0;
}
</endl;></head-></bits>
#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) { Node* slow = head; Node* fast = head; while(fast!=tail && fast->next!=tail){ slow = slow->next; fast = fast->next->next; } Node* afterMiddle = slow->next; slow->next = NULL; return afterMiddle; } /* merge sort*/ Node* mergeSort(Node* head){ if(head == NULL || head->next == NULL){ return head; } Node* tail = head; while(tail->next){ tail = tail->next; } Node* afterMiddle = middle(head, tail); Node* part1 = mergeSort(head); 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 */ void printList(Node* head){ while(head != NULL){ cout<<head->data<<" "; head = head->next; } cout<<endl; }="" *="" function="" to="" find="" the="" intersection="" list="" node*="" intersectionlist(node*="" list1,="" list2){="" if(list1="=" null="" ||="" list2="=NULL){" return="" null;="" intersectionhead="NULL;" intersectiontail="NULL;" while(list1="" &&="" if(list1-="">data == list2->data){ if(intersectionHead == NULL && intersectionTail == NULL){ intersectionHead = list1; 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; return intersectionHead; } /* function to insert a node at the beginning of a linked list*/ Node* push(Node* head, int new_data){ Node* new_node = new Node(new_data); /* link the old list with the new node */ new_node->next = head; /* move the head to point to the new node */ head = new_node; return head; } int main() { /* Start with the empty list */ Node* head1 = NULL; Node* head2 = NULL; Node* list_intersection = NULL; /*create a new linked lits 10->15->4->20 */ head1 = push(head1, 20); head1 = push(head1, 4); head1 = push(head1, 15); head1 = push(head1, 10); /*create a new linked lits 8->4->2->10 */ head2 = push(head2, 10); head2 = push(head2, 2); head2 = push(head2, 4); head2 = push(head2, 8); cout << "First list " << endl; printList(head1); cout << "Second list " << endl; printList(head2); head1 = mergeSort(head1); head2 = mergeSort(head2); list_intersection = intersectionList(head1, head2); cout << "Intersection list " << endl; printList(list_intersection); return 0; } </endl;></head-></bits>
#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) {
        Node* slow = head;
        Node* fast = head;
        
        while(fast!=tail && fast->next!=tail){
            slow = slow->next;
            fast = fast->next->next;
        }
        Node* afterMiddle = slow->next;
        slow->next = NULL;
        return afterMiddle;
}
 
/* merge sort*/
Node* mergeSort(Node* head){
    if(head == NULL || head->next == NULL){
        return head;
    }
 
    Node* tail = head;
 
    while(tail->next){
        tail = tail->next;
    }
 
 
    Node* afterMiddle = middle(head, tail);
    Node* part1 = mergeSort(head);
    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 */
void printList(Node* head){
    while(head != NULL){
        cout<data<<" ";
        head = head->next;
    }
    cout<data == list2->data){
            if(intersectionHead == NULL && intersectionTail == NULL){
                intersectionHead = list1;
                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;
    return intersectionHead;
}
 
/* function to insert a node at the beginning of a linked list*/
Node* push(Node* head, int new_data){
 
    Node* new_node = new Node(new_data);
 
    /* link the old list with the new node */
    new_node->next = head;
 
    /* move the head to point to the new node */
    head = new_node;
 
    return head;
}
 
int main()
{
   
    /* Start with the empty list */
    Node* head1 = NULL;
    Node* head2 = NULL;
    Node* list_intersection = NULL;
 
    /*create a new linked lits 10->15->4->20 */
    head1 = push(head1, 20);
    head1 = push(head1, 4);
    head1 = push(head1, 15);
    head1 = push(head1, 10);
 
    /*create a new linked lits 8->4->2->10 */
    head2 = push(head2, 10);
    head2 = push(head2, 2);
    head2 = push(head2, 4);
    head2 = push(head2, 8);
    
 
    cout << "First list " << endl;
    printList(head1);
    cout << "Second list " << endl;
    printList(head2);
    
    head1 = mergeSort(head1);
    head2 = mergeSort(head2);
    
    list_intersection = intersectionList(head1, head2);    
    cout << "Intersection list " << endl;
    printList(list_intersection);
    return 0;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def middle(head, tail):
slow = head
fast = head
while fast != tail and fast.next != tail:
slow = slow.next
fast = fast.next.next
afterMiddle = slow.next
slow.next = None
return afterMiddle
def mergeSort(head):
if head == None or head.next == None:
return head
tail = head
while tail.next:
tail = tail.next
afterMiddle = middle(head, tail)
part1 = mergeSort(head)
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
def printList(head):
while head:
print(head.data, end=" ")
head = head.next
def intersectionList(head1, head2):
result = LinkedList()
t1 = head1
t2 = head2
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
return result.head
head1 = Node(20)
head1.next = Node(4)
head1.next.next = Node(15)
head1.next.next.next = Node(10)
head2 = Node(10)
head2.next = Node(2)
head2.next.next = Node(4)
head2.next.next.next = Node(8)
head1 = mergeSort(head1)
head2 = mergeSort(head2)
list_intersection = intersectionList(head1, head2)
print("First list")
printList(head1)
print("\nSecond list")
printList(head2)
print("\nIntersection list")
printList(list_intersection)
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def middle(head, tail): slow = head fast = head while fast != tail and fast.next != tail: slow = slow.next fast = fast.next.next afterMiddle = slow.next slow.next = None return afterMiddle def mergeSort(head): if head == None or head.next == None: return head tail = head while tail.next: tail = tail.next afterMiddle = middle(head, tail) part1 = mergeSort(head) 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 def printList(head): while head: print(head.data, end=" ") head = head.next def intersectionList(head1, head2): result = LinkedList() t1 = head1 t2 = head2 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 return result.head head1 = Node(20) head1.next = Node(4) head1.next.next = Node(15) head1.next.next.next = Node(10) head2 = Node(10) head2.next = Node(2) head2.next.next = Node(4) head2.next.next.next = Node(8) head1 = mergeSort(head1) head2 = mergeSort(head2) list_intersection = intersectionList(head1, head2) print("First list") printList(head1) print("\nSecond list") printList(head2) print("\nIntersection list") printList(list_intersection)
class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:
	
	def __init__(self):
		self.head = None

	def push(self, new_data):

		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node


def middle(head, tail):

	slow = head
	fast = head

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

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

def mergeSort(head):

	if head == None or head.next == None:
		return head

	tail = head

	while tail.next:
		tail = tail.next

	afterMiddle = middle(head, tail)
	part1 = mergeSort(head)
	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

def printList(head):
	while head:
		print(head.data, end=" ")
		head = head.next

def intersectionList(head1, head2):

	result = LinkedList()
	t1 = head1
	t2 = head2

	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

	return result.head

head1 = Node(20)
head1.next = Node(4)
head1.next.next = Node(15)
head1.next.next.next = Node(10)

head2 = Node(10)
head2.next = Node(2)
head2.next.next = Node(4)
head2.next.next.next = Node(8)

head1 = mergeSort(head1)
head2 = mergeSort(head2)

list_intersection = intersectionList(head1, head2)

print("First list")
printList(head1)
print("\nSecond list")
printList(head2)

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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) {
Node* slow = head;
Node* fast = head;
while(fast!=tail && fast->next!=tail){
slow = slow->next;
fast = fast->next->next;
}
Node* afterMiddle = slow->next;
slow->next = NULL;
return afterMiddle;
}
/* merge sort*/
Node* mergeSort(Node* head){
if(head == NULL || head->next == NULL){
return head;
}
Node* tail = head;
while(tail->next){
tail = tail->next;
}
Node* afterMiddle = middle(head, tail);
Node* part1 = mergeSort(head);
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 */
void printList(Node* head){
while(head != NULL){
cout<<head->data<<" ";
head = head->next;
}
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* uniHead = NULL;
Node* uniTail = NULL;
while(list1 && list2){
if(list1->data == list2->data){
if(uniHead == NULL && uniTail == NULL){
uniHead = list1;
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){
uniHead = list2;
uniTail = list2;
}else{
uniTail->next = list2;
uniTail = list2;
}
list2 = list2->next;
}else if(list2->data > list1->data){
if(uniHead == NULL && uniTail == NULL){
uniHead = list1;
uniTail = list1;
}else{
uniTail->next = list1;
uniTail = list1;
}
list1 = list1->next;
}
}
return uniHead;
}
/* function to insert a node at the beginning of a linked list*/
Node* push(Node* head, int new_data){
Node* new_node = new Node(new_data);
/* link the old list with the new node */
new_node->next = head;
/* move the head to point to the new node */
head = new_node;
return head;
}
int main()
{
/* Start with the empty list */
Node* head1 = NULL;
Node* head2 = NULL;
Node* list_union = NULL;
/*create a new linked lits 10->15->4->20 */
head1 = push(head1, 20);
head1 = push(head1, 4);
head1 = push(head1, 15);
head1 = push(head1, 10);
/*create a new linked lits 8->4->2->10 */
head2 = push(head2, 10);
head2 = push(head2, 2);
head2 = push(head2, 4);
head2 = push(head2, 8);
cout << "First list " << endl;
printList(head1);
cout << "Second list " << endl;
printList(head2);
head1 = mergeSort(head1);
head2 = mergeSort(head2);
list_union = unionList(head1, head2);
cout << "Union List " << endl;
printList(list_union);
return 0;
}
#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) { Node* slow = head; Node* fast = head; while(fast!=tail && fast->next!=tail){ slow = slow->next; fast = fast->next->next; } Node* afterMiddle = slow->next; slow->next = NULL; return afterMiddle; } /* merge sort*/ Node* mergeSort(Node* head){ if(head == NULL || head->next == NULL){ return head; } Node* tail = head; while(tail->next){ tail = tail->next; } Node* afterMiddle = middle(head, tail); Node* part1 = mergeSort(head); 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 */ void printList(Node* head){ while(head != NULL){ cout<<head->data<<" "; head = head->next; } 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* uniHead = NULL; Node* uniTail = NULL; while(list1 && list2){ if(list1->data == list2->data){ if(uniHead == NULL && uniTail == NULL){ uniHead = list1; 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){ uniHead = list2; uniTail = list2; }else{ uniTail->next = list2; uniTail = list2; } list2 = list2->next; }else if(list2->data > list1->data){ if(uniHead == NULL && uniTail == NULL){ uniHead = list1; uniTail = list1; }else{ uniTail->next = list1; uniTail = list1; } list1 = list1->next; } } return uniHead; } /* function to insert a node at the beginning of a linked list*/ Node* push(Node* head, int new_data){ Node* new_node = new Node(new_data); /* link the old list with the new node */ new_node->next = head; /* move the head to point to the new node */ head = new_node; return head; } int main() { /* Start with the empty list */ Node* head1 = NULL; Node* head2 = NULL; Node* list_union = NULL; /*create a new linked lits 10->15->4->20 */ head1 = push(head1, 20); head1 = push(head1, 4); head1 = push(head1, 15); head1 = push(head1, 10); /*create a new linked lits 8->4->2->10 */ head2 = push(head2, 10); head2 = push(head2, 2); head2 = push(head2, 4); head2 = push(head2, 8); cout << "First list " << endl; printList(head1); cout << "Second list " << endl; printList(head2); head1 = mergeSort(head1); head2 = mergeSort(head2); list_union = unionList(head1, head2); cout << "Union List " << endl; printList(list_union); return 0; }
#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) {
        Node* slow = head;
        Node* fast = head;
        
        while(fast!=tail && fast->next!=tail){
            slow = slow->next;
            fast = fast->next->next;
        }
        Node* afterMiddle = slow->next;
        slow->next = NULL;
        return afterMiddle;
}
 
/* merge sort*/
Node* mergeSort(Node* head){
    if(head == NULL || head->next == NULL){
        return head;
    }
 
    Node* tail = head;
 
    while(tail->next){
        tail = tail->next;
    }
 
 
    Node* afterMiddle = middle(head, tail);
    Node* part1 = mergeSort(head);
    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 */
void printList(Node* head){
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
    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* uniHead = NULL;
    Node* uniTail = NULL;
 
    while(list1 && list2){
        if(list1->data == list2->data){
            if(uniHead == NULL && uniTail == NULL){
                uniHead = list1;
                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){
                uniHead = list2;
                uniTail = list2;
            }else{
                uniTail->next = list2;
                uniTail = list2;
            }
 
            list2 = list2->next;
        }else if(list2->data > list1->data){
            if(uniHead == NULL && uniTail == NULL){
                uniHead = list1;
                uniTail = list1;
            }else{
                uniTail->next = list1;
                uniTail = list1;
            }
 
            list1 = list1->next;
        }
    }
 
    return uniHead;
}
 
/* function to insert a node at the beginning of a linked list*/
Node* push(Node* head, int new_data){
 
    Node* new_node = new Node(new_data);
 
    /* link the old list with the new node */
    new_node->next = head;
 
    /* move the head to point to the new node */
    head = new_node;
 
    return head;
}

int main()
{   
    /* Start with the empty list */
    Node* head1 = NULL;
    Node* head2 = NULL;
    Node* list_union = NULL;
 
    /*create a new linked lits 10->15->4->20 */
    head1 = push(head1, 20);
    head1 = push(head1, 4);
    head1 = push(head1, 15);
    head1 = push(head1, 10);
 
    /*create a new linked lits 8->4->2->10 */
    head2 = push(head2, 10);
    head2 = push(head2, 2);
    head2 = push(head2, 4);
    head2 = push(head2, 8);
    
 
    cout << "First list " << endl;
    printList(head1);
    cout << "Second list " << endl;
    printList(head2);
    
    head1 = mergeSort(head1);
    head2 = mergeSort(head2);
    
    list_union = unionList(head1, head2);
    
    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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post