### 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.

``````
/**
* 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!