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

## Comments

## Post a Comment