Merge Two Sorted Lists
You are given the heads of two sorted linked lists. Merge the two sorted linked lists into one sorted linked list. The list should be made by splicing together the nodes of the first two lists.
Constraints:
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- 0 <= i <= list1.length + list2.length
Examples:
Input: [1,2,4] and [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: The lists are merged into one sorted list.
Solutions
Iterative Approach
Time: O(n + m)Space: O(n + m)
We create a dummy node to simplify the code and avoid dealing with special cases for the head of the result list. We then iterate through both lists, comparing the current nodes and appending the smaller one to the result list. Finally, we append the remaining nodes from either list.
class Solution:
def mergeTwoLists(self, l1:
ListNode, l2:
ListNode) -> ListNode:
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.nextFollow-up:
How would you handle the case where the input lists are not sorted?
