Union intersection Two Linked Lists Using Merge Sort

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

#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;
}

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

#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.

Introduction

Problem Statement

Input:

Output:

Algorithm for Intersection

Dry Run

Code Implementation

Output

Algorithm for Union

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply

Types of Algorithm Analysis

Why Analysis of Algorithms is important?

What is meant by Algorithm Analysis?

Design and Analysis of Algorithms

Timestamp Based Concurrency Control

Multiple Granularity Locking in DBMS

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Introduction

Problem Statement

Input:

Output:

Algorithm for Intersection

Dry Run

Code Implementation

Output

Algorithm for Union

Dry Run

Code Implementation

Output

Leave a Reply Cancel reply