21. Merge Two Sorted Lists

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.

Approach : Here is the simple recursive solution to solve the problem:

1. Base case : Return one of the lists if another is NULL
2. Else recursively call the function with appropriate values of two current nodes' values

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b) {
    struct ListNode* result = NULL;  
   /* Base cases */  
   if (a == NULL)  
     return(b);  
   else if (b == NULL)  
     return(a);  
   /* Pick either a or b, and recur */  
   if (a->val <= b->val) {  
     result = a;  
     result->next = mergeTwoLists(a->next, b);  
   }else {  
     result = b;  
     result->next = mergeTwoLists(a, b->next);  
   }  
   return(result); 
}

Here is the link to the ideone solution : https://ideone.com/V6zDKA