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) {
        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;
}

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
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<data<<" ";
        head = head->next;
    }
    cout<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.

Previous post Josephus Circle Using Circular Linked List
Next post Merge K Sorted Doubly Linked List in Sorted Order

Leave a Reply

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