Ticker

6/recent/ticker-posts

Header Ads Widget

Responsive Advertisement

Merge two sorted linked lists



/* Link list Node
struct Node {
  int data;
  struct Node *next;
  
  Node(int x) {
    data = x;
    next = NULL;
  }
};
*/
Node* sortedMerge(Node* head1, Node* head2)  
{  
    Node*temp1=head1;
    Node*temp2=head2;
    Node*Dummy=new Node(-1);
    Node*ab=Dummy;
    while(temp1!=NULL && temp2!=NULL)
    {
        if(temp1->data >= temp2->data)
        {
            Node*temp=new Node(temp2->data);
            ab->next=temp;
            temp->next=NULL;
            ab=temp;
            temp2=temp2->next;
        }
        else{
             Node*temp=new Node(temp1->data);
            ab->next=temp;
            temp->next=NULL;
            ab=temp;
            temp1=temp1->next;
        }
    }
    while(temp1!=NULL)
    {
        Node*temp=new Node(temp1->data);
        ab->next=temp;
        temp->next=NULL;
        ab=temp;
        temp1=temp1->next;
    }
    while(temp2!=NULL)
    {
        Node*temp=new Node(temp2->data);
        ab->next=temp;
        temp->next=NULL;
        ab=temp;
        temp2=temp2->next;
    }
    Dummy=Dummy->next;
    return Dummy;
}  */


// Now we will do recursively 
Node* sortedMerge(Node* head1, Node* head2)  
{  
    if(head1==NULL)
    {
        return head2;
    }
    if(head2==NULL)
    {
        return head1;
    }
    Node*result;
    if(head1->datadata)
    {
        result=head1;
        result->next=sortedMerge(head1->next,head2);
    }
    else{
        result=head2;
        result->next=sortedMerge(head1,head2->next);
    }
    return result;
}  

Post a Comment

0 Comments