Description
Merge two ascending linked lists by relinking their existing nodes. Return the merged head.
Solution
def merge_two_lists(list1, list2):
dummy = tail = ListNode()
while list1 and list2:
if list1.val <= list2.val:
tail.next, list1 = list1, list1.next
else:
tail.next, list2 = list2, list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.nextExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,5],[2,4]]- Output
[1,2,4,5]
Taking the smaller head produces 1, 2, 4, 5.
Example 2
- Input
[[],[]]- Output
[]
There are no nodes to merge.
Example 3
- Input
[[],[3]]- Output
[3]
The nonempty list becomes the result.
Approach
Use a dummy head and repeatedly attach the smaller front node.
Time & space
O(n + m) time; O(1) space. Here n is the input length.