Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

Union and Intersection of Two Linked Lists

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
Linked List

Introduction

This blog will discuss the various approaches to solving the Union and the Intersection of two Linked Lists. Before jumping into the problem of getting the Union and Intersection of two Linked Lists, let’s first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

Singly Linked List

You can refer to this link for more information on the linked list.

In this Union and Intersection of two Linked Lists problem, we need to return the head of the linked list after taking the union and intersection of two linked lists regardless of the order of the nodes in the linked list.

Note: Duplicates are not present in the same linked list.

For Example:-

List1 :- 10 -> 15 -> 45 -> 17 -> 145 

List2 :- 145 -> 5 -> 11 -> 45 -> 43 -> 1 

Union List :-  45 -> 15 -> 10 -> 17 -> 145 -> 145 -> 45 -> 11 -> 5 -> 43 -> 1 -> 75 

Intersection List :- 145 -> 45

Brute Force Approach

Brute Force Solution considers traversing the ‘list2’ and checking each element with an element of ‘list 1’, if the same element is present, then we just have to add that element in the intersection list, whereas, for the union list, we just need to add all the elements of ‘list1’ in union list, and when traversing the ‘list2’, if that particular element is already present in ‘list1’, then skip that element and if that element is not present in the ‘list1’ then we just need to add that element in the union list.

Algorithm for Union 

Step 1. Create a function ‘getUnion()’ that will accept two parameters, i.e., one head pointer of the linked list 1, one head pointer of the linked list 2.

Step 2. Initialize a resultant union list ‘unionList’ with a NULL value, and two variables ‘temp1’ with the head of linked list1 and ‘temp2’ with the head of linked list2.

Step 3. Make an iteration using the ‘while’ loop to traverse linked list 1 with the help of ‘temp1’, which will terminate when ‘temp1’ is equal to the NULL value.

Step 4. Create a function ‘helper’ to push all the given elements in the given ‘head’ of the linked list, and with the help of this ‘helper’ function, we have to push all the nodes during the iteration.

Step 5. Assign the value of the pointer of the ‘next’ node of ‘temp1’ to ‘temp1’.

Step 6. Make an iteration using the ‘while’ loop to traverse linked list 2 with the help of the ‘temp2’, which will terminate when ‘temp2’ is equal to the NULL value.

Step 7. Create a boolean function ‘present’, which will take two parameters, one will be the head of the resultant ‘UnionList’, and the other will be the data of that respective ‘temp2’ which we need to check.

Step 8. Check if the node of the same data is already present in the resultant linked list or not using the ‘present’ function.

  • If it is not present, then we need to push the same element in the resultant ‘unionList’ linked list using the ‘helper’ function.

Step 9. Assign the value of the pointer of the next node of the ‘temp2’ to ‘temp2’.

Step 10. Return the pointer of the head of the resultant ‘UnionList’ linked list.

Algorithm for Intersection

Step 1. Create a function ‘getIntersection()’ that will accept two parameters, i.e., one head pointer of the linked list 1, one head pointer of the linked list 2.

Step 2. Initialize a resultant intersection list ‘intersectionList’ with a NULL value, and two variable ‘temp’ with the head of linked list1.

Step 3. Make an iteration using the ‘while’ loop to traverse linked list 1 with the help of ‘temp1’, which will terminate when ‘temp1’ is equal to the NULL value.

Step 4. Check with the help of the ‘present’ function, if the element of the same value is present in the other linked list or not.

  • If it is present, then push that element in the resultant ‘intersectionList’ using the ‘helper’ function.

Step 5. Assign the value of pointer of next node of ‘temp’ to ‘temp’

Step 6. Return the pointer of the head of ‘intersectionList’.

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

// Linked list's node's structure
struct Node {
    int data;
    struct Node * next;
};

// Add node to the list
void push(struct Node ** head_ref, int new_data) {
    struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));

    // Insert Data
    new_node -> data = new_data;

    // Link it with the list
    new_node -> next = ( * head_ref);

    // Increment the head pointer
    ( * head_ref) = new_node;
}

// Check the presence of the data
bool present(struct Node * head, int data) {
    struct Node * temp = head;
    while (temp != NULL) {
        if (temp -> data == data)
            return 1;
        temp = temp -> next;
    }
    return 0;
}

/* Function to get union of two
linked lists head1 and head2 */
struct Node * getUnion(
    struct Node * head1,
    struct Node * head2) {
    struct Node * result = NULL;
    struct Node * t1 = head1, * t2 = head2;

    // Insert all elements of
    // list1 to the result list
    while (t1 != NULL) {
        push( & result, t1 -> data);
        t1 = t1 -> next;
    }

    // Insert those elements of list2
    // which are not present in result list
    while (t2 != NULL) {
        if (!present(result, t2 -> data))
            push( & result, t2 -> data);
        t2 = t2 -> next;
    }
    return result;
}

/* Function to get intersection of
two linked lists head1 and head2 */
struct Node * getIntersection(struct Node * head1, struct Node * head2) {
    struct Node * result = NULL;
    struct Node * temp1 = head1;

    // Traverse the first linked list
    while (temp1 != NULL) {
        if (present(head2, temp1 -> data))
            push( & result, temp1 -> data);
        temp1 = temp1 -> next;
    }
    return result;
}

// Print the linked list
void printList(struct Node * node) {
    while (node != NULL) {
        cout << " " << node -> data;
        node = node -> next;
    }
}

int main() {

    // Empty list
    struct Node * head1 = NULL;
    struct Node * head2 = NULL;
    struct Node * intersectionList = NULL;
    struct Node * unionList = NULL;

    // First Linked List
    push( & head1, 10);
    push( & head1, 15);
    push( & head1, 45);
    push( & head1, 17);
    push( & head1, 145);

    // Second Linked List
    push( & head2, 145);
    push( & head2, 5);
    push( & head2, 11);
    push( & head2, 45);
    push( & head2, 43);
    push( & head2, 1);

    intersectionList = getIntersection(head1, head2);
    unionList = getUnion(head1, head2);
    cout << "Given First linked list:-";
    printList(head1);
    cout << endl;
    cout << "Given Second linked list:-";
    printList(head2);
    cout << endl;
    cout << "Intersection Linked list:-";
    printList(intersectionList);
    cout << endl;
    cout << "Union linked list:-";
    printList(unionList);
    cout << endl;
}

 

Output :

Given Linked List1:- 10 -> 15 -> 45 -> 17 -> 145 
Given Linked List2:- 145 -> 5 -> 11 -> 45 -> 43 -> 1 
Union:-  45 -> 15 -> 10 -> 17 -> 145 -> 145 -> 45 -> 11 -> 5 -> 43 -> 1 -> 75 
Intersection:- 145 -> 45

Complexity Analysis

Time Complexity: O(M * N) 

As we are working on two linked lists of sizes ‘M’ and ‘N’ respectively, and for both union and intersection, we are comparing each element of a linked list with the complete other linked list, therefore, the overall time complexity will be O(M * N). 

Space Complexity: O(N)

As we are using constant space, therefore, the overall space complexity will be O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

To optimize this Union and Intersection of two Linked Lists, we’ll try to optimize the time complexity with the help of hashing technique. We need to traverse both the linked list’s and store all the elements in the map along with the number of occurrences of that particular element. In case of union, we need to store all the elements of the map in the ‘unionList’ and return its head pointer and in case of intersection, we just need to store those elements from the map, whose occurrences are 2 which depicts that it is stored in both the linked lists.

Algorithm

Step 1. In the function call ‘getResult()’, it takes three parameters:- first will be the pointer to the head of the linked list 1, and the second will be the pointer to the head of the linked list 2. 

Step 2. Create an unordered map ‘map’ of int type.

Step 3. Make an iteration using the ‘while’ loop which will terminate when both the pointers to both the linked lists will be equal to null.

Step 4.  Add the element in the map by increasing its occurrence in the map if the pointer to linked list 1 is not equal to null.

Step 5.  Similarly, Add the element in the map by increasing its occurrence in the map if the pointer to linked list 2 is not equal to null.

Step 6. Initialize an object of class ‘Node’ named as ‘unionList’ which will store the resultant nodes from the union of both the linked lists.

Step 7. Iterate the ‘map’ and insert all the elements of the ‘map’ to the ‘unionList’ using the ‘push’ function.

Step 8. Print the ‘unionList’ using the ‘print’ function.

Step 9. Initialize an object of class ‘Node’ named as ‘intersectionList’ which will store the resultant nodes from the intersection of both the linked lists.

Step 10. Iterate the ‘map’ and insert all the elements of the ‘map’ with occurrences equal to 2 using the ‘push’ function.

Step 11. Print the ‘intersectionList’ using the ‘print’ function.

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

// Link list node
struct Node {
    int data;
    struct Node * next;
};

// Add node to the linked list
void push(struct Node ** head_ref, int new_data) {
    /* allocate node */
    struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));

    // Insert Data
    new_node -> data = new_data;

    // Link the node with the linked list
    new_node -> next = ( * head_ref);

    // Increment the header pointer
    ( * head_ref) = new_node;
}

// Store elements
void helper(struct Node * head1, struct Node * head2, unordered_map < int, int > & mp) {
    struct Node * temp1 = head1;
    struct Node * temp2 = head2;

    // Traverse both linked lists
    while (temp1 != NULL || temp2 != NULL) {
        // store element in the map
        if (temp1 != NULL) {
            mp[temp1 -> data]++;
            temp1 = temp1 -> next;
        }

        // store element in the map
        if (temp2 != NULL) {
            mp[temp2 -> data]++;
            temp2 = temp2 -> next;
        }
    }
}

// Union of both the linked list
struct Node * getUnion(unordered_map < int, int > mp) {
    struct Node * result = NULL;

    for (auto it = mp.begin(); it != mp.end(); it++)
        push( & result, it -> first);

    return result;
}

// Intersection of both the linked list
struct Node * getIntersection(unordered_map < int, int > mp) {
    struct Node * result = NULL;

    for (auto it = mp.begin(); it != mp.end(); it++)
        if (it -> second == 2)
            push( & result, it -> first);

    // return resultant linked list
    return result;
}

void printList(struct Node * node) {
    while (node != NULL) {
        printf("%d ", node -> data);
        node = node -> next;
    }
}

void printUnionIntersection(Node * head1, Node * head2) {
    // Store all the elements of
    // both lists in the map
    unordered_map < int, int > mp;
    helper(head1, head2, mp);

    Node * intersection_list = getIntersection(mp);
    Node * union_list = getUnion(mp);

    printf("\nIntersection list is \n");
    printList(intersection_list);

    printf("\nUnion list is \n");
    printList(union_list);
}

/* Driver program to test above function*/
int main() {
    /* Start with the empty list */
    struct Node * head1 = NULL;
    struct Node * head2 = NULL;

    /* create a linked list 11->10->15->4->20 */
    push( & head1, 10);
    push( & head1, 15);
    push( & head1, 45);
    push( & head1, 17);
    push( & head1, 145);

    /* create a linked list 8->4->2->10 */
    push( & head2, 145);
    push( & head2, 5);
    push( & head2, 11);
    push( & head2, 45);
    push( & head2, 43);
    push( & head2, 1);

    printf("First list is \n");
    printList(head1);

    printf("\nSecond list is \n");
    printList(head2);

    printUnionIntersection(head1, head2);

    return 0;
}

 

Output :

Given Linked List1:- 10 -> 15 -> 45 -> 17 -> 145 
Given Linked List2:- 145 -> 5 -> 11 -> 45 -> 43 -> 1 
Union:-  45 -> 15 -> 10 -> 17 -> 145 -> 145 -> 45 -> 11 -> 5 -> 43 -> 1 -> 75 
Intersection:- 145 -> 45

Complexity Analysis

Time Complexity: O(M + N)

Incall to ‘getResult()’, we are just traversing both linked lists of size ‘M’ and ‘N’, respectively, therefore, the overall time complexity is O(M + N).

Space Complexity: O(M + N)

As we are using the unordered Map data structure for storing a maximum of M + N values, therefore, the overall space complexity is O(M + N).

Frequently Asked Questions

What are the types of Linked list?

A linked list is of three types:- Singly Linked List, Doubly Linked List, and Circular Linked List.

What is the difference between a Singly Linked List and a Doubly Linked List?

In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers of its next node and its previous node. 

What is the Circular Linked List?

In Circular Linked List, the tail of the linked list points to the head of the same linked list.

Conclusion

In this article, we discussed the What is Union and Intersection of two Linked Lists problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, All the best for your future endeavors, and Keep Coding.

Topics covered
1.
Introduction
2.
Brute Force Approach
2.1.
Algorithm for Union 
2.2.
Algorithm for Intersection
2.3.
Implementation in C++
2.3.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the types of Linked list?
4.2.
What is the difference between a Singly Linked List and a Doubly Linked List?
4.3.
What is the Circular Linked List?
5.
Conclusion