Union and Intersection of two Linked Lists

Harsh Goyal
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

This blog will discuss the various approaches to solve 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.

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 two linked list of size ‘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).

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 the 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 Hash Map data structure for storing a maximum of M + N values, therefore, the overall space complexity is O(M + N).

Frequently asked questions

1) What are the types of the Linked list?

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

 

2) What is the difference between Singly Linked List and Doubly Linked List?

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

 

3) What is the Circular Linked List?

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

Key takeaways

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. 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

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

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think