Union and Intersection of two Linked Lists

Union and Intersection of two Linked Lists” is one of the foremost problem asked in many technical and algorithmic interviews of product based companies. Here, we are given two linked list and our task is to write a program to find the union and intersection between given two linked list. 

The order of elements in union list and intersection list does not matter.

Note: It is assumed that both lists do not contain any duplicates.

For example, we need to find the union and intersection of two linked list:
List1: 12 -> 34 -> 88 -> 56 -> 66
List2: 34 -> 67 -> 66 -> 33 ->98
Union list: 12 -> 34 -> 88 -> 56 -> 66 -> 67 -> 33 -> 98
Intersection list: 34 -> 66

The steps required to find the union and intersection of two linked lists are as follows:

UNION:

  1. Initialize the resultant union list as NULL.
  2. Now, assign resultant union list to List1.
  3. Traverse List2, and, for each element in List2, if it is present in resultant list, ignore it, otherwise, if it is not present in the resultant list, add it to resultant list.

INTERSECTION:

  1. Initialize the resultant intersection list as NULL.
  2. Now, traverse the list1, for every element of list1, traverse the list2, if that element is present in list2, then add the element in the resultant list. Otherwise, ignore the element.

C++ Program to find Union and Intersection of two Linked Lists is as follows:

/* C++ Program to find union and intersection of two linked list */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the node of the linked list */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert node at the end of the linked list */
void insert_end(Node **head, int ele)
{
    /* Creating a new node */
    Node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
     
    /* If Linked List is empty, then new node will become head of the linked list */
    if(*head == NULL)    
    {
        *head = new_node;
        return;
    }
    
    /* If Linked List is not empty, then traverse the complete linked list and point the pointer
    of last node of the linked list to the new node */
    Node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to find union of two linked list  */
Node *findUnion(Node *head1 , Node *head2)
{
    Node *res = NULL;
    Node *ptr = res;
    Node *temp = head1;
    /* Copy and create all the nodes from first linked list to resultant linked list*/
    while(temp != NULL)
    {
        Node *new_node;
        new_node = (struct node*)malloc(sizeof(struct node));
        new_node->data = temp->data;
        new_node->next = NULL;
        if(res == NULL)
        {
            res = new_node;
            ptr = res;
        }
        else
        {
            ptr -> next = new_node;
            ptr = ptr -> next;
        }
        temp = temp -> next;
    }
    temp = head2;
    /* For every node present in second linked list, first check whether is it already present
    in resultant linked list or not. If already present, igonre it, else create a new node and 
    copy the data of the second linked list*/
    while(temp != NULL)
    {
        Node *temp2 = res;
        bool var = false;
        while(temp2 != NULL)
        {
            if(temp->data == temp2->data)
            {
                var = true;
                break;
            }
            temp2 = temp2 -> next;
        }
        if(var == false)
        {
            Node *new_node;
            new_node = (struct node*)malloc(sizeof(struct node));
            new_node->data = temp->data;
            new_node->next = NULL;
            if(res == NULL)
            {
                res = new_node;
                ptr = res;
            }
            else
            {
                ptr -> next = new_node;
                ptr = ptr -> next;
            }        
        }
        temp = temp -> next;
    }
    return res;
}

/* Function to find intersection between two Linked List */
Node *findIntersection(Node *head1 , Node *head2)
{
    Node *res = NULL;
    Node *ptr = NULL;
    Node *temp1 = head1;
    /*
        For every node present in first node, if the same is present in second linked list,
        then only, create new node and copy the data of the data insert it into Intersection
        linked list
    */
    while(temp1 != NULL)
    {
        Node *temp2 = head2;
        bool var = true;
        while(temp2 != NULL)
        {
            if(temp1 -> data == temp2 -> data)
            {
                var = false;
                break;
            }
            temp2 = temp2 -> next;
        }
        if(var == false)
        {
            Node *new_node;
            new_node = (struct node*)malloc(sizeof(struct node));
            new_node->data = temp1->data;
            new_node->next = NULL;
            if(res == NULL)
            {
                res = new_node;
                ptr = res;
            }
            else
            {
                ptr -> next = new_node;
                ptr = ptr -> next;
            }        
        }
        temp1 = temp1 -> next;
    }
    return res;
}

/* Function to print the Linked List */
void print(Node *head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    Node *head1 , *head2;
    
    head1 = NULL;
    head2 = NULL;
    /* Inserting Some Nodes in the First Linked List */
    insert_end(&head1,12);
    insert_end(&head1,34);
    insert_end(&head1,88);
    insert_end(&head1,56);
    insert_end(&head1,66);
    
    /* Inserting Some Nodes in the Second Linked List */
    insert_end(&head2,34);
    insert_end(&head2,66);
    insert_end(&head2,61);
    insert_end(&head2,33);
    insert_end(&head2,98);
    
    cout<<"First Linked List:\n";
    print(head1);
    
    cout<<"\nSecond Linked List:\n";
    print(head2); 
    
    Node *Union = findUnion(head1 , head2);
    Node *Intersection = findIntersection(head1 , head2);
    
    cout<<"\nUnion of Two Linked List:\n";
    print(Union);
    
    cout<<"\nIntersection Between Two Linked List:\n";
    print(Intersection);
    
}
OUTPUT:
First Linked List:
12 34 88 56 66
Second Linked List:
34 66 61 33 98
Union of Two Linked List:
12 34 88 56 66 61 33 98
Intersection Between Two Linked List:
34 66

Related Posts:

  1. Merge Two Sorted Linked List.
  2. Insert a New Node at the Sorted Linked List.
  3. Reverse a Linked List.
  4. Reverse a Linked List Using Stack.
  5. Printing Linked List in Reverse Order without actually reversing the Linked List.
  6. Swap Adjacent Elements of the Linked List.
  7. Count All Occurrences of a Particular Node in a Linked List.
  8. Bubble Sort on Linked List.
  9. Detect a Loop in a Linked List.
  10. Find the Length of the Loop present in the Linked List.
  11. Detect and Remove Loop from a Linked List.
  12. Segregate Even and Odd Nodes of the Linked List.
  13. Delete Complete Linked List.
  14. Delete Nth Node of the Linked List.
  15. Delete without head pointer of the Linked List.
  16. Delete All Occurrences of particular node of the Linked List.
  17. Delete Alternate Nodes of the Linked List.
  18. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  19. Remove Duplicate Nodes from an Unsorted Linked List.
  20. Remove Duplicate Nodes from a Sorted Linked List.

You may also like...