Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list and return its head.
Constraints:
- The number of nodes in both lists is in the range
[0, 100]. - Node values are in the range
[-100, 100].
Example 1:
Input: list1 = [1, 2, 4], list2 = [1, 3, 5] Output: [1, 1, 2, 3, 4, 5]
Example 2:
Input: list1 = [], list2 = [] Output: []
Recommended time and space complexity
You should aim for a solution with O(n + m) time complexity and O(1) space complexity for the iterative approach or O(n + m) for the recursive approach, where n and m are the lengths of the lists.
Hint 1
A brute force approach would be to create a new list and copy elements from both lists in the correct order. This would be an O(n + m) time and O(n + m) space solution. Can you think of a more efficient approach?
Hint 2
Can you merge the lists by changing the links between nodes without using additional memory?
Hint 3
Use two pointers to traverse the lists and merge nodes by choosing the smaller element at each step.