Merge Two Sorted Lists
Problem Description
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
list1andlist2are sorted in non-decreasing order.
Solve it on LeetCode
Approaches
1. Iterative Merge Approach
Intuition:
The easiest way to merge two sorted lists is to use an iterative approach. We can start by creating a dummy node that acts as a placeholder for the start of the merged list. We then use a current pointer to iterate through both lists and append the smaller node to the current node until we reach the end of one of the lists. Finally, we append any remaining nodes from the non-empty list.
Code:
- Time Complexity: O(n + m) where n and m are the lengths of the input lists.
- Space Complexity: O(1) since no additional space proportional to input size is used.
2. Recursive Merge Approach
Intuition:
Alternatively, we can use a recursive solution to merge the two lists. The recursive approach involves merging the first nodes of each list, followed by the recursively merged result of the remainder of the lists. This is achieved by continually selecting the smaller head node between the two lists until all nodes have been merged.
Code:
- Time Complexity: O(n + m) where n and m are the lengths of the input lists, as each node is only visited once.
- Space Complexity: O(n + m) due to the recursion stack, which holds a frame for each recursive call.