Merge Two Sorted Lists
You're given the heads of two singly linked lists, list1 and list2, each already sorted in non-decreasing order. Combine them into a single sorted list by linking together the existing nodes rather than creating new ones, and return the head of the combined list. Either list may be empty. If both are empty, return null.
Examples
list1 = [1,2,4], list2 = [1,3,4] returns [1,1,2,3,4,4]
Every node from both lists appears exactly once, and the values read 1, 1, 2, 3, 4, 4 from smallest to largest.
list1 = [], list2 = [] returns []
Both lists are empty, so the combined list is empty too (return null).
list1 = [], list2 = [0] returns [0]
With list1 empty, the answer is simply list2 as it is.
Constraints
- 0 <= number of nodes in each list <= 50
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
Hints
At any moment, the next node of the answer has to be one of the two nodes at the front of the lists.
This is the two-list case of a k-way merge. A dummy node plus a tail pointer lets you append nodes without special-casing the head.
Loop while both lists are non-empty: link the smaller front after tail, then advance that list and tail. After the loop, set tail.next to whichever list remains and return dummy.next.
Drill This: Your Approach First
Approach
Use a dummy head and a tail pointer. While both lists have nodes, compare their fronts, link the smaller one after tail and advance that list. When one list runs out, attach the rest of the other in one step, since it is already sorted. Each node is linked exactly once and no new nodes are created. O(m + n) time, O(1) extra space, where m and n are the list lengths.
Time
O(m + n)
Space
O(1)
Pitfall
Solutions
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next;
}
tail.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}from typing import Optional
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
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 if list1 else list2
return dummy.next