Merge Two Sorted Lists
Merge Two Sorted Lists is an easy Linked List problem from the Blind 75. The key pattern is two-pointer merge, and a good solution runs in O(n + m) time.
Problem
Merge two non-decreasing linked-list value arrays into one non-decreasing list.
Examples
Example 1
Input
[[1,4,9],[2,3,10]]Output
[1,2,3,4,9,10]Example 2
Input
[[],[]]Output
[]Example 3
Input
[[2,2,5],[1,4]]Output
[1,2,2,4,5]Approach
Use a placeholder head and repeatedly attach the smaller front value, then append whatever remains of the other list.
| Pattern | Two-pointer merge |
|---|---|
| Time | O(n + m) |
| Space | O(1) |
Watch out for
Equal values may come from either list; keep the result non-decreasing.