Node<int>* sortTwoLists(Node<int>* first, Node<int>* second)
{
Node<int>* head1=first;
Node<int>* head2= second;
Node<int>* ans=NULL;
while(head1!=NULL && head2!=NULL){
if(head1->data<head2->data){
Node<int>* tmp= new Node<int>(head1->data);
tmp->next=ans;
ans=tmp;
head1=head1->next;
//free(tmp);
}else{
Node<int>* tmp= new Node<int>(head2->data);
tmp->next=ans;
ans=tmp;
head2=head2->next;
//free(tmp);
}
}
while(head1!=NULL){
Node<int>* tmp= new Node<int>(head1->data);
tmp->next=ans;
ans=tmp;
head1=head1->next;
}
while(head2!=NULL){
Node<int>* tmp= new Node<int>(head2->data);
tmp->next=ans;
ans=tmp;
head2=head2->next;
}
//reverse ll
Node<int>* curr=ans;
Node<int>* prev=NULL;
Node<int>* forward=NULL;
while(curr!=NULL){
forward=curr->next;
curr->next=prev;
prev=curr;
curr=forward;
}
ans=prev;
return ans;
}