Merge Two Sorted Lists
Easy
Linked List
Recursion
You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists into 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*.
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]

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.
Time Complexity
O(m + n)
Space Complexity
O(1)
14
Case 1
Input: [1,2,4] [1,3,4]
Expected: [1,1,2,3,4,4]
Case 2
Input: [] []
Expected: []
Case 3
Input: [] [0]
Expected: [0]