Home >>Cpp Programs >C++ Program to find Union of two singly Linked Lists

C++ Program to find Union of two singly Linked Lists

C++ Program to find Union of two singly Linked Lists

In this example, we will see a C++ program through which we will find the union of two single linked list.

In this program, we can use either the Brute force technique or the Merge sort technique.

In Brute force, we have to include all the nodes of a linked list and for other linked checks whether nodes are already appended or not. This approach can take O(m*n) times complexity.

In Merge sort technique first sort both the linked list using merge sort then Scan each linked list and build a union, and finally display the union list.

Program:


#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...
2 26 39 82 94 56 48 73 6 81 73 19 0

Cpp Programs Fibonacci Series in C++ Armstrong Number in C++ Factorial program in C++ Check Palindrome in C++ Prime Number Program In C++ Reverse Number Program in C++ Sum Of Digits Program in C++ C++ Find C++ protected keyword CPP Program for different ways to print array elements CPP Program to determine the colour of chess square CPP Program to Reverse Number CPP Program to Calculate Power of a Number CPP Program to print all Even and Odd numbers from 1 to N Program to find whether a no is power of two in CPP C++ program to find largest list of prime numbers Auto keyword in Cpp C++ program to print the left Rotation of the array Convert a given binary Tree to Doubly Linked List Delete keys in a Linked list using C++ program How do you delete a linked list in C++ Implement stack with linked list in c++ C++ Program to find first occurrence of a Number Using Recursion in an array C++ program to find Last occurrence of a Number using Recursion in an array C++ Program to find Union of two singly Linked Lists Remove Duplicates from linked list in c++ C++ Program to find Nth node in Linked List Merge sort singly linked list c++ C++ Program to Convert Roman Number to Integer Number C++ Program to find LCM of two numbers C++ Password Generator C++ Program to multiply two numbers without using multiplication operator C++ Program to print all possible subset of a set Sum of all the elements in an array divisible by a given number Print First uppercase letter in a string c++ C++ Program to Find the Number Occurring Odd Number of Times C++ Program for Print address of Variable Using Pointer C++ Program to Find ASCII Value of a Character C++ Classes and Objects Program Create a class method in C++ C++ Create Empty Class Define a class method outside the class definition in C++ How to create multiple objects of a class in C++