Merge 2 sorted lists

This is one of leetcode’s daily challenges.

The problem statement is as follows:

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

SAMPLE INPUT AND OUTPUT:

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2 :

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

This problem is rated as “easy” by leetcode. The solution for this problem is also unlocked.

As cited in leetcode itself, this problem can be solved using either the recursive approach or using the iterative approach.

RECURSIVE APPROACH

The recursive approach, works based on the intuition that the problem can be solved by recursively finding the smaller element of the two lists and by setting the next element of our result to the merge operation on the remaining elements of the 2 lists.

Edge cases:

1. l1 or l2 is initially null.

CODE :

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }
        else if (l2 == NULL) {
            return l1;
        }
        else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
        
    }
};

ITERATIVE APPROACH:

We create additional answer ListNode, and append the lesser of the 2 input linked lists to this node accordingly.

CODE :

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode ans(0), *it = &ans;
        
        
        while(l1 || l2){
            if(l1 && l2){
                if(l1->val < l2->val){
                    it->next = l1;
                    l1 = l1->next;
                }
                else{
                    it->next = l2;
                    l2 = l2->next;
                }
                
            }
            else if(l1){
                it->next = l1;
                l1 = l1->next;
                
            }
            else if(l2){
                it->next = l2;
                l2 = l2->next;
                
            }
            it = it->next;
            
        }
        return ans.next; 
        
    }
};

TIME COMPLEXITY:
It is O(n+m), where n is the length of the first list and m is the length of second list. This is because, exactly one of l1 or l2 is incremented in each iteration. All the other work runs in constant time.

SPACE COMPLEXITY:

Recursive : O(n+m) The first call to mergeTwoLists does not return until the ends of both l1 and l2 have been reached, so n + mn+m stack frames consume O(n + m) space.

Iterative : O(1) The iterative approach only allocates a few pointers, so it has a constant overall memory footprint.