C++: Merge Two Sorted Lists

Thought Process

To merge two sorted linked lists, we can either use a recursive approach or an iterative approach:

Approach 1: Recursive Approach - Handle edge cases where one of the lists is empty. Compare the current nodes of both lists. Recursively merge the remaining lists and link the smaller node to the result.

Approach 2: Iterative Approach - Start by handling edge cases where one of the lists is empty. Ensure list1 always points to the smaller starting node. Use a prev pointer to keep track of the last node in the merged list. Traverse both lists, appending the smaller node to the merged list and updating pointers.

Approach 1: Recursive Approach 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        if(list1==NULL)
            return list2;

        if(list2==NULL)
            return list1;

        if(list1->val < list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }
        else{
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

Approach 2: Iterative Approach 

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* &list1, ListNode* &list2) {

        if(list1==NULL)
            return list2;

        if(list2==NULL)
            return list1;

        if(list1->val > list2->val){
            ListNode* tmp = list1;
            list1 = list2;
            list2 = tmp;
        }

        ListNode* newHead = list1;
        while(list1!=NULL && list2!=NULL){

            ListNode* prev = NULL;
            while(list1!=NULL && list1->val <= list2->val){
                prev  = list1;
                list1 = list1->next;
            }
            prev->next = list2;
            ListNode* tmp = list1;
            list1 = list2;
            list2 = tmp;
        }
        return newHead;
    }
};

Code Complexity

Time Complexity: O(n + m)

Both approaches iterate through all nodes of the two lists, where 'n' and 'm' are the lengths of the two lists.

Space Complexity: O(n + m) or O(1)

The recursive approach uses stack space proportional to the sum of the lengths of the two lists, while the iterative approach uses constant space.

Code copied!