# C++ program to find Union of two single Linked Lists

In this article, we are going to see how to find union of two linked list efficiently using merge sorting?
Submitted by Radib Kar, on December 27, 2018

Problem statement: Write a C++ program to find the union of two single linked lists.

Example:

```    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
```

Solution

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++ implementation 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;
};

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

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{
}

}

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);
node* head1=creatnode(k); //buliding list, first node
scanf("%d",&k);

///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
temp=temp->next;
scanf("%d",&k);
}
cout<<"displaying list1...\n";
cout<<"\nenter list2...\n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);

///////////////////inserting at the end//////////////////////
while(k){
curr=creatnode(k);
temp->next=curr;//appending each node
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
```

Top MCQs

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates