You are given the heads of two sorted linked lists, list1 and list2. Merge them into one sorted list by splicing together their existing nodes, and return the head of the merged list.
- Each list has 0 to 50 nodes
- -100 <= Node.val <= 100
- Both lists are sorted in non-decreasing order
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One brute force collects all values, sorts them and builds a new list: O((m + n) log(m + n)) with extra nodes. Since both lists are already sorted, the smallest remaining value is always at the front of one of them, just like the merge step of merge sort. A dummy head avoids special-casing the first node: we keep appending the smaller front node to tail, and when one list is empty we link the remainder of the other in one step.
Algorithm
- Create a
dummynode and settail = dummy. - While both lists are non-empty, attach the node with the smaller value to
tail.nextand advance that list. - Move
tailto the node just attached. - When one list is empty, set
tail.nextto the other list (it is already sorted). - Return
dummy.next.
O(m + n)Space: O(1)<= when comparing so equal values keep their original order (a stable merge). The recursive version is shorter but uses O(m + n) stack space; mention it if asked.class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0) # fixed start, avoids head special cases 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 # attach the leftover part return dummy.next