CODE:
#include
using namespace std;
class node{
public:
int data;
node*next;
//constructor
node(int d)
{
data=d;
next=NULL;
}
};
void insertAtHead(node*&head,int d) {
if(head==NULL){
head=new node(d);
return;
}
node*n=new node(d);
n->next=head;
head=n;
}
void print(node*head)
{
while(head!=NULL)
{
cout<data<<" ";
head=head->next;
}
cout<<endl;
}
node* take_input_2(int n){
int d;
cin>>d;
node head=NULL;
while(n–){
insertAtHead(head,d);
cin>>d;
}
return head;
}
node midpoint(nodehead){
if(head==NULL or head->next==NULL){
return head;
}
node slow=head;
nodefast=head->next;
while(fast!=NULL and fast->next!=NULL){
fast =fast->next->next;
slow=slow->next;
}
return slow;
}
node merge(nodea,nodeb)
{
if(a==NULL){
return b;
}
if(b==NULL){
return a;
}
node c;
if(a->datadata){
c=a;
c->next=merge(a->next,b);
}
else{
c=b;
c->next=merge(a,b->next);
}
return c;
}
node mergeSort(nodehead){
//Base Case
if(head==NULL or head->next==NULL){
return head;
}
//Recursive Case
//1.Divide The Linked List
nodemid=midpoint(head);
nodea=head;
nodeb=mid->next;
mid->next=NULL;
//2. rec Sort the two parts
a=mergeSort(a);
b=mergeSort(b);
//3.Merge Them
node*c=merge(a,b);
return c;
}
int main(){
int T;
cin>>T;
while(T–){
int n;
cin>>n;
node head1=take_input_2(n);
cin>>n;
node head2=take_input_2(n);
nodenewHead=merge(head1,head2);
nodenewHead2=mergeSort(newHead);
print(newHead2);
}
}
2 is not coming in the final answer .
Can u Pls tell me the mistake