Merge Two Sorted Lists
Easy
Linked ListRecursion
You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists into one **sorted** list by splicing together the nodes of the two lists. Return the head of the merged linked list.
**Example 1:**
```
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
```
**Example 2:**
```
Input: list1 = [], list2 = [0]
Output: [0]
```
Expected Time Complexity
O(n + m)
Expected Space Complexity
O(1)
Example Test Cases
Example 1
Input:
[1,2,4] [1,3,4]
Output:
[1,1,2,3,4,4]
Example 2
Input:
[] [0]
Output:
[0]