Home »
C++ programs
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.
- Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
- Scan each linked list and build union according to following:
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
- 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;
};
void display(class node* head){
node* current=head; // current node set to head
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){
node* newhead=NULL;
//base cases
if(split1==NULL)
return split2;
if(split2==NULL)
return split1;
if(split1->data<=split2->data){
newhead=split1;
newhead->next=mergeList(split1->next,split2);
}
else{
newhead=split2;
newhead->next=mergeList(split1,split2->next);
}
return newhead;
}
void splitList(node* head,node** split1,node** split2){
node* slow=head;
node* fast=head->next;
while(fast!=NULL){
fast=fast->next;
if(fast!=NULL){
slow=slow->next;
fast=fast->next;
}
}
*split1=head;
*split2=slow->next;
//spliting
slow->next=NULL;
}
void mergeSort(node** refToHead){
node* head=*refToHead;
node* split1,*split2;
//base case
if(head==NULL || head->next==NULL){
return;
}
//split the list in two halves
splitList(head,&split1,&split2);
//recursively sort the two halves
mergeSort(&split1);
mergeSort(&split2);
*refToHead=mergeList(split1,split2);
return;
}
node* findUnion(node* head1, node* head2){
if(head1==NULL && head2==NULL)
return NULL;
node* head3;
if(head1->data<head2->data){
head3=creatnode(head1->data);
head1=head1->next;
}
else if(head1->data==head2->data){
head3=creatnode(head1->data);
head1=head1->next;
head2=head2->next;
}
else{
head3=creatnode(head2->data);
head2=head2->next;
}
node* temp=head3;
while( head1!=NULL && head2!=NULL){
if(head1->data<head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
}
else if(head1->data==head2->data){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
head2=head2->next;
}
else{
temp->next=creatnode(head2->data);
temp=temp->next;
head2=head2->next;
}
}
while(head1!=NULL){
temp->next=creatnode(head1->data);
temp=temp->next;
head1=head1->next;
}
while(head2!=NULL){
temp->next=creatnode(head2->data);
temp=temp->next;
head2=head2->next;
}
return head3;
}
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);
temp=head1;
///////////////////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";
display(head1); // displaying the list
cout<<"\nenter list2...\n";
scanf("%d",&k);
node* head2=creatnode(k); //buliding list, first node
scanf("%d",&k);
temp=head2;
///////////////////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";
display(head2);
//sort both the lists
mergeSort(&head1);
mergeSort(&head2);
cout<<"\ndisplaying their union...\n";
node* head3=findUnion(head1,head2);
display(head3);
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
Second linked list:3->8->9->12->1->NULL
After applying merge sort:
First linked list: 1->3->4->5->6->NULL
Second linked list: 1->3->8->9->12->NULL
---------------------------------------------------------
//for better understanding nodes are represented only by respective values
head1=1
head2=1
FindUnion(1,1):
0th iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=1
thus head3(head of union list) =1
temp=head3=1
union list up to now:
1->NULL
head1=1->next=3;
head2=1->next=3;
1st iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=3
thus temp->next =3
temp=temp->next=3;
union list up to now:
1->3->NULL
head1=3->next=4;
head2=3->next=8;
2nd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //4<8
thus temp->next =head1->data=4
temp=temp->next=4;
union list up to now:
1->3->4->NULL
head1=4->next=5;
3rd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //5<8
thus temp->next =head1->data=5
temp=temp->next=5;
union list up to now:
1->3->4->5->NULL
head1=5->next=6;
4th iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //6<8
thus temp->next =head1->data=6
temp=temp->next=6;
union list up to now:
1->3->4->5->6->NULL
head1=6->next=NULL;
5th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=8
temp=temp->next=8;
union list up to now:
1->3->4->5->6->8->NULL
head2=8->next=9;
6th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=9
temp=temp->next=9;
union list up to now:
1->3->4->5->6->8->9->NULL
head2=9->next=12;
7th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=12
temp=temp->next=12;
union list up to now: 1->3->4->5->6->8->9->12->NULL
head2=12->next=NULL;
8th iteration:
head1==NULL
head2==NULL
thus no more scanning, union list is built
union: 1->3->4->5->6->8->9->12->NULL
Head3 at 1