Merge Two Sorted Lists
EasyZip two sorted lists with a dummy head
Zip two sorted chains together by always attaching the smaller front box next.
The idea
Use a dummy node to simplify edge cases. Repeatedly attach the smaller of the two front nodes and advance that list. Append whatever remains.
1
3
8
Step 1 of 7. Merge sorted A = [1,3,8] and B = [2,4,5] — attach the smaller head each step.
1/7
Optimal
timeO(n+m)spaceO(1)
Splice nodes in order.
1const dummy = new Node(); let tail = dummy;2while (a && b) {3 if (a.val <= b.val) { tail.next = a; a = a.next; }4 else { tail.next = b; b = b.next; }5 tail = tail.next;6}7tail.next = a ?? b;8return dummy.next;Input
- list
- [1, 3, 8]
Memory
- A head
- —
- B head
- —
Output
- merged
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = 1 -> 2 -> 4, b = 1 -> 3 -> 4
- Output:
- 1 -> 1 -> 2 -> 3 -> 4 -> 4
- Explanation:
- Zip the two sorted lists together.
Example 2
- Input:
- a = , b = 0
- Output:
- 0
- Explanation:
- One empty → the other list.
Example 3
- Input:
- a = 5, b = 1 -> 2
- Output:
- 1 -> 2 -> 5
- Explanation:
- Interleave to 1,2,5.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.