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

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

You can also try this code with Online C++ Compiler

Run Code

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 - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

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!