
Challenge Statement
- You are given the heads of two sorted linked lists
list1
andlist2
. - 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
andlist2
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.