Leetcode: 21. Merge Two Sorted Lists (Recursion)

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The resulting list should be created by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
        {
            return list2; 
        }
        else if (list2 == nullptr)
        {
            return list1;
        }
        else if (list1->val < list2->val)
        {
            list1->next =  mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

Time Complexity

The time complexity of the mergeTwoLists function is O(n + m), where n and m are the lengths of list1 and list2 respectively. This is because in each recursive call, we either move to the next node in list1 or list2, until we reach the end of one of the lists.

Example

Let's consider an example to understand how the mergeTwoLists function works. Suppose we have two sorted linked lists:

list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6

After merging list1 and list2 using the mergeTwoLists function, we would get the following merged list:

1 -> 2 -> 3 -> 4 -> 5 -> 6

In this example, the mergeTwoLists function compares the values of the nodes in list1 and list2 at each step and links them together in ascending order. The resulting merged list contains all the nodes from both input lists, arranged in a sorted manner.

Hope this helps!