Union and Intersection of two Linked Lists

Union and Intersection of two Linked Lists

This article explains how we can do the union and intersection of two linked lists. In this problem, we have given two linked lists and find the union and intersection of these given two lists. Here we will not consider the order of output list elements.

Example:

Input:

                        List1: 1 -> 8 -> 4 -> 2

                        List2:  3 -> 4 -> 6 -> 2

Output:

                        Intersection of the Lists: 4 -> 2

                        Union of the Lists: 1 -> 8 -> 4 -> 2 -> 3 -> 6

Method:

The following are simple algorithms to get union and intersection lists, respectively.

Intersection (list1, list2):

Firstly, we will initialize the result list with NULL, then we will traverse the list1, and we will check every element in list2. If the elements of the list1 present in the list2, we will add the elements to the resultant list.

Union (list1, list2):

In this section, we will first initialize the result list with NULL. Then, we will traverse the list1 and add all of its elements to the result list. Then, we traverse the list2. If the element of list2 is already present in the result list, we will skip those elements. Else, we will add the rest of its elements to the result list.

C Program to implement the union and intersection of the linked list

 #include<stdio.h>
 #include<stdlib.h>
 struct node
 {
 int info;
 struct node * next;
 };
 struct node * start1 = NULL, * start2 = NULL, * res = NULL;
 int len = 0, n;
 // For inserting the elements in the linked list
 void add(int item, struct node **temp)
 {
 struct node * t, * p;
 t = (struct node * )malloc( sizeof( struct node ));
 if(*temp == NULL)
 {
 * temp = t;
 (* temp) -> info = item;
 (* temp) -> next = NULL;
 return;
 }
 else
 {
 struct node * p = * temp;
 while(p -> next != NULL)
 {
 p = p -> next;
 }
 p -> next = t;
 p = p -> next;
 p -> info = item;
 p -> next = NULL;
 }
 }
 // Function of finding the union of two linked list
 struct node* getUnion(struct node* head1, struct node* head2)
 {
     struct node * result = NULL;
     struct node * t1 = head1, * t2 = head2;
     while (t1 != NULL) {
         add(t1 -> info, &result);
         t1 = t1 -> next;
     }
     while (t2 != NULL) {
         if (!isPresent(result, t2 -> info))
             add(t2 -> info, &result);
         t2 = t2 -> next;
     }
     return result;
 }
 // Function of finding the intersection of two linked list
 struct node * getIntersection(struct node * head1,
                              struct node * head2)
 {
     struct node * result = NULL;
     struct node * t1 = head1;
     while (t1 != NULL) {
         if (isPresent(head2, t1 -> info))
             add(t1-> info,&result);
         t1 = t1-> next;
     }
     return result;
 }
 // Function for checking the elements
 int isPresent(struct node * head, int info)
 {
     struct node * t = head;
     while (t != NULL) {
         if (t -> info == info)
             return 1;
         t = t -> next;
     }
     return 0;
 }
 // To display the elements of the linked list
 void traverse(struct node * t)
 {
  if(t == NULL)
 {
             printf(" Linked list is empty\n");
 }
 while(t -> next != NULL)
 {
                         printf("%d -> ", t -> info);
                         t = t -> next;
 }
                         printf("%d\n", t -> info);
 }
 // Driver Function
 int main()
 {
 // Add element into the linked1
     add(1, &start1);
     add(10, &start1);
     add(3, &start1);
     add(4, &start1);
     add(9, &start1);
     add(8, &start1);
 // Add element into the linked2
     add(1, &start2);
     add(10, &start2);
     add(3, &start2);
     add(6, &start2);
     add(2, &start2);
     add(8, &start2);
     printf("list1: ");
     traverse(start1);
     printf("list2: ");
     traverse(start2);
     res = getUnion(start1, start2);
     printf("Union is: ");
     traverse(res);
     res = getIntersection(start1, start2);
     printf("Intersection is: ");
     traverse(res);
     return 0;
 } 

Output:

Time Complexity: The time complexity of the above method is O(m*n), where m and n are the numbers of elements present in the first and second linked list, respectively.