## Challenge Statement

- You are given the heads of two sorted linked lists
`list1`

and`list2`

. - Merge the two lists in a one
**sorted**list. The list should be made by splicing together the nodes of the first two lists.*.* - Return
*the head of the merged linked list*. - This challenge corresponds to LeetCode #21.

### Constraints

- The number of nodes in both lists is in the range
`[0, 50]`

. `-100 <= Node.val <= 100`

- Both
`list1`

and`list2`

are sorted in**non-decreasing**order.

**Example 1:**

**Input:** `list1 = [1, 2, 4]`

, `list2 = [1, 3, 4]`

**Output:** `[1, 1, 2, 3, 4, 4]`

**Example 2:**

**Input:** `list1 = []`

, `list2 = []`

**Output:** `[]`

**Example 3:**

**Input:**` list1 = []`

, `list2 = [0]`

**Output:** `[0]`

## Solution

Below is my solution and some test cases. This solution has a **linear time complexity O(n) and a constant space complexity O(1)**, where n is the length of the input list*.*