# Union and Intersection of two Linked Lists

Difficulty Level Medium
Frequently asked in 24*7 Innovation Labs Accolite Amazon Flipkart Komli Media Microsoft Taxi4Sure VMware Walmart Labs

Given two linked lists, create another two linked lists to get union and intersection of the elements of existing lists.

## Example

Input:

List1: 5 → 9 → 10 → 12 → 14

List2: 3 → 5 → 9 → 14 → 21

Output:

Intersection_list: 14 → 9 → 5

Union_list:   21 → 14 → 12 → 10 → 9 → 5 → 3

Explanation: A linked list is the collection of nodes. Every node is connected in sequence. We can get the intersection and union of two linked lists by using several methods. But, the efficient method to use in this case is first, sort both the linked list using merge sort and then linearly check both the sorted linked list to get intersection and union of both linked lists. Here, the merge sort is often preferred for sorting of the linked list than other algorithms that perform poorly.

## Algorithm

1. Create a linked list by declaring the head and next pointer of the list.
2. Insert the elements in both the list using insert func.
3. Sort both linked lists using the merge sort algorithm.
4. Finally, linearly scan both the sorted list to get the union and intersection of the list.

## Explanation

First, we create a node by creating a Node class in our program So, that we could create our Linked list. In our program, we create two unordered linked list. After that, we sort both the linked list by using our sorting algorithm and then we create our function to get the union and intersection of our linked lists. After sorting both the linked lists it easy to scan them linearly such that we could get union and intersection of our linked lists.

## Implementation

### C++ program for Union and Intersection of two Linked Lists

```#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
int value;
struct Node* next;
};

void insert(struct Node** head, int new_value)
{
struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));

NewNode->value = new_value;

}

void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
struct Node* fast;
struct Node* slow;
if (source==NULL || source->next==NULL)
{
*front = source;
*back = NULL;
}
else
{
slow = source;
fast = source->next;

while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}

*front = source;
*back = slow->next;
slow->next = NULL;
}
}

struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
struct Node* result = NULL;

if (fst == NULL)
return(sec);
else if (sec==NULL)
return(fst);

if (fst->value <= sec->value)
{
result = fst;
result->next = Sort_merge(fst->next, sec);
}
else
{
result = sec;
result->next = Sort_merge(fst, sec->next);
}
return(result);
}

{
struct Node *a, *b;

return;

Sort(&a);
Sort(&b);

}

{
struct Node *result = NULL;

while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
{
insert(&result, t1->value);
t1 = t1->next;
}

else if (t1->value>t2->value)
{
insert(&result, t2->value);
t2 = t2->next;
}
else
{
insert(&result, t2->value);
t1 = t1->next;
t2 = t2->next;
}
}

while (t1 != NULL)
{
insert(&result, t1->value);
t1 = t1->next;
}
while (t2 != NULL)
{
insert(&result, t2->value);
t2 = t2->next;
}

return result;
}

{
struct Node *result = NULL;

while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
t1 = t1->next;

else if (t1->value > t2->value)
t2 = t2->next;

else
{
insert(&result, t2->value);

t1 = t1->next;
t2 = t2->next;
}
}

return result;
}

void printList (struct Node *node)
{
while (node != NULL)
{
cout<<node->value << " ";
node = node->next;
}
cout<<endl;
}

int main()
{
struct Node* intersection_list = NULL;
struct Node* union_list = NULL;

cout<<"First list is \n";

cout<<"\nSecond list is \n";

cout<<"\nIntersection list is \n";
printList(intersection_list);

cout<<"\nUnion list is \n";
printList(union_list);

return 0;
}
```
```First list is
4 10 11 15 20

Second list is
2 4 8 10

Intersection list is
10 4

Union list is
20 15 11 10 8 4 2```

### Java program for Union and Intersection of two Linked Lists

```class Solution1
{

class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

void get_union(Node hd1, Node hd2)
{
Node t1 = hd1, t2 = hd2;

while (t1 != null)
{
insert(t1.data);
t1 = t1.next;
}

while (t2 != null)
{
insert(t2.data);
t2 = t2.next;
}
}

void get_intrSection(Node hd1, Node hd2)
{
Node rst = null;
Node t1 = hd1;

while (t1 != null)
{
if (is_Present(hd2, t1.data))
insert(t1.data);
t1 = t1.next;
}
}

void printList()
{
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

void insert(int new_data)
{

Node new_node = new Node(new_data);

}

{
while (t != null)
{
if (t.data == data)
return true;
t = t.next;
}
return false;
}

public static void main(String args[])
{
Solution1 llist1 = new Solution1();
Solution1 llist2 = new Solution1();
Solution1 unin = new Solution1();
Solution1 intersecn = new Solution1();

llist1.insert(20);
llist1.insert(4);
llist1.insert(15);
llist1.insert(10);

llist2.insert(10);
llist2.insert(2);
llist2.insert(4);
llist2.insert(8);

System.out.println("First List is");
llist1.printList();

System.out.println("Second List is");
llist2.printList();

System.out.println("Intersection List is");
intersecn.printList();

System.out.println("Union List is");
unin.printList();
}
}
```
```First List is
10 15 4 20
Second List is
8 4 2 10
Intersection List is
4 10
Union List is
2 8 20 4 15 10```

## Complexity Analysis for Union and Intersection of two Linked Lists

### Time Complexity

O(m+n) where “m” and “n” are the number of elements present in first and second lists respectively.

### Space Complexity

O(m+n) where “m” and “n” are the number of elements present in first and second lists respectively.

Translate »