Merge two sorted linked lists

PROBLEM :

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

For example if the first linked list a is 5->10->15 and the other linked list b is 2->3->20, then SortedMerge() should return a pointer to the head node of the merged list 2->3->5->10->15->20.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
 
    struct ListNode *n1,*n2,*temp,*merge,*ptr ;
    merge=NULL ;
    n1=l1 ;
    n2=l2 ;
 
    while(n1!=NULL&&n2!=NULL)
    {
        temp=(struct ListNode*)malloc(sizeof(struct ListNode)) ;
        temp->next=NULL ;
     
        if(n1->val<n2->val)
        {
            temp->val=n1->val ;
            n1=n1->next ;
        }
        else
        {
            temp->val=n2->val ;
            n2=n2->next ;
        }
     
        if(merge==NULL)
            merge=temp ;
        else
        {
            ptr=merge ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=temp ;
        }
    }
 
    if(n1!=NULL)
    {
        if(merge==NULL)
            merge=n1 ;
        else
        {
            ptr=merge ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=n1 ;
        }
    }
 
    if(n2!=NULL)
    {
        if(merge==NULL)
            merge=n2 ;
        else
        {
            ptr=merge ;
            while(ptr->next!=NULL)
                ptr=ptr->next ;
            ptr->next=n2 ;
        }
    }
 
    return merge ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Better INPLACE solution (without using 3rd List))
--------------------------------------------------------------------------------

/* Link list Node
struct Node {
    int data;
    Node* next;
}; */

Node* SortedMerge(Node* head1,   Node* head2)
{
    if(head1==NULL)
        return head2 ;
       
    Node * temp1,*temp2,*temp3,*temp ;
    temp1=head1 ;
    temp2=head2 ;
    temp3=NULL ;
   
    while(temp1!=NULL&&temp2!=NULL)
    {
        if(temp1->data>temp2->data)
        {
            temp=temp2 ;
            temp2=temp2->next ;
           
            if(temp3!=NULL)
            {
                temp->next=temp3->next ;
                temp3->next=temp ;
                temp1=temp ;
            }
            else
            {
                head1=temp ;
                temp->next=temp1 ;
                temp1=temp ;
            }
        }
        else
        {
            temp3=temp1 ;
            temp1=temp1->next ;
        }
    }
   
    if(temp2!=NULL)
        temp3->next=temp2 ;
       
    return head1 ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Better INPLACE solution (using Recursion)
--------------------------------------------------------------------------------

/* Link list Node
struct Node {
    int data;
    Node* next;
}; */

Node* SortedMerge(Node* head1,   Node* head2)
{
    Node *ans=NULL ;
    if(head1==NULL)
        return head2 ;
    if(head2==NULL)
        return head1 ;
       
    if(head1->data<head2->data)
    {
        ans=head1 ;
        ans->next=SortedMerge(head1->next,head2) ;
    }
    else
    {
        ans=head2 ;
        ans->next=SortedMerge(head1,head2->next) ;
    }
    return ans ;
}

---------------------------------------------------------------------------------