The problem
Given the heads of two linked lists, list1 and list2, each already sorted from smallest to largest, splice their nodes into one sorted list and return its head.
Examples
01
- Input
list1 = [1, 2, 4], list2 = [1, 3, 4]
- Output
[1, 1, 2, 3, 4, 4]
02
- Input
list1 = [], list2 = []
- Output
[]
03
- Input
list1 = [], list2 = [0]
- Output
[0]
Constraints
- 0 ≤ nodes in each list ≤ 50
- −100 ≤ Node.val ≤ 100
- Both lists are sorted in non-decreasing order.
The idea
The smallest node overall is the smaller of the two fronts. Take it, and the question repeats on what is left — so walk both lists at once, always taking the smaller front.
A dummy node — a placeholder at the start of the answer — means the first node needs no special case: tail starts on the dummy and each chosen node is hung after it. When one list runs out, the rest of the other is already sorted and is attached in one step.
- Time
- O(n + m) — each node is taken once
- Space
- O(1) — the nodes are relinked, not copied
Solution · every language run against every case
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = tail = ListNode() # a placeholder in front of the result 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 # whatever is left is already sorted return dummy.next