# C++ program to find union of two single linked lists

Find union of two single linked lists: In this tutorial, we will learn how to find the union of two single linked lists with the help of multiple approaches using the C++ programs? By Radib Kar Last updated : August 01, 2023

## Problem statement

Given two singly linked lists, write a C++ program to find the union of two given singly-linked lists.

Consider the below example with sample input and output:

```Let the first linked list be:
5->4->3->6->1->NULL

Let the second linked list to be:
3->8->9->12->1->NULL

So there union is:
5->4->3->6->1->8->9->12->NULL
```

## Brute force approach

One technique can be to include all the nodes of a linked list and for other linked check whether nodes are already appended or not. Such an approach takes O(m*n) times complexity. m, n=length of linked lists.

## Efficient approach

Efficient approach use to use merge sort.

1. Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
2. Scan each linked list and build union according to following:
3. ```IF (list1->data < list2->data)
Createnode(list1->data) && append node to the union list
Traverse list1 by one step( list1=list1->next)
ELSE IF(list1->data ==list2->data)
Createnode(list1->data) && append nodeto the union list
Traverse list1 by one step( list1=list1->next)
Traverse list2 by one step( list2=list2->next)
ELSE//list1->data >list2->data
Createnode(list2->data) && append node to the union list
Traverse list2 by one step( list2=list2->next)
END IF-ELSE
```
4. Display the union list

## C++ program to find union of two single linked lists

```#include <bits/stdc++.h>
using namespace std;

class node {
public:
int data; // data field
struct node* next;
};

{
// current node set to head
//traverse until current node isn't NULL
while (current != NULL) {
printf("%d ", current->data);
// go to next node
current = current->next;
}
}

node* creatnode(int d)
{
node* temp = (node*)malloc(sizeof(node));
temp->data = d;
temp->next = NULL;
return temp;
}
node* mergeList(node* split1, node* split2)
{
//base cases
if (split1 == NULL)
return split2;
if (split2 == NULL)
return split1;

if (split1->data <= split2->data) {
}
else {
}

}

void splitList(node* head, node** split1, node** split2)
{

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

*split2 = slow->next;
//spliting
slow->next = NULL;
}

{
node *split1, *split2;
//base case
return;
}
//split the list in two halves
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);

return;
}

{
return NULL;

}

}
else {

}

temp = temp->next;
}

temp = temp->next;

}
else {
temp = temp->next;
}
}

temp = temp->next;
}
temp = temp->next;
}

}

int main()
{
printf("creating the linked list by inserting new nodes at the end\n");
printf("enter 0 to stop building the list, else enter any integer\n");

int k;
node *curr, *temp;

cout << "enter list1...\n";
scanf("%d", &k);

//buliding list, first node
scanf("%d", &k);

//inserting at the end
while (k) {
curr = creatnode(k);
//appending each node
temp->next = curr;
temp = temp->next;
scanf("%d", &k);
}

cout << "displaying list1...\n";
// displaying the list

cout << "\nenter list2...\n";
scanf("%d", &k);

//buliding list, first node
scanf("%d", &k);

//inserting at the end
while (k) {
curr = creatnode(k);
//appending each node
temp->next = curr;
temp = temp->next;
scanf("%d", &k);
}

cout << "displaying list1...\n";

//sort both the lists

cout << "\ndisplaying their union...\n";

return 0;
}
```

## Output

```creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
5 4 3  6 1 0
displaying list1...
5 4 3 6 1
enter list2...
3 8 9 12 1 0
displaying list1...
3 8 9 12 1
displaying their union...
1 3 4 5 6 8 9 12
```

## Example with explanation

```First linked list: 5->4->3->6->1->NULL

After applying merge sort:
---------------------------------------------------------

//for better understanding nodes are represented only by respective values
FindUnion(1,1):

0th iteration
union list up to now:
1->NULL

1st iteration
thus temp->next =3
temp=temp->next=3;
union list up to now:
1->3->NULL

2nd iteration
temp=temp->next=4;
union list up to now:
1->3->4->NULL

3rd iteration
temp=temp->next=5;
union list up to now:
1->3->4->5->NULL

4th iteration
temp=temp->next=6;
union list up to now:
1->3->4->5->6->NULL

5th iteration
temp=temp->next=8;
union list up to now:
1->3->4->5->6->8->NULL

6th iteration
temp=temp->next=9;
union list up to now:
1->3->4->5->6->8->9->NULL

7th iteration
temp=temp->next=12;
union list up to now: 1->3->4->5->6->8->9->12->NULL

8th iteration:
thus no more scanning, union list is built

union: 1->3->4->5->6->8->9->12->NULL