#21 Merge Two Sorted Lists
You're given the heads of two linked lists, each already sorted in ascending order. Splice them into one sorted list, reuse the existing nodes rather than allocating new ones, and return its head. Either input (or both) may be empty.
Examples
Input
list1 = 1 → 2 → 4, list2 = 1 → 3 → 4Output
1 → 1 → 2 → 3 → 4 → 4Nodes are interleaved by value; duplicates across lists all survive.
Input
list1 = null, list2 = nullOutput
nullTwo empty lists merge to an empty list.
Input
list1 = null, list2 = 0Output
0One empty side means the answer is just the other list.
Constraints
0 ≤ nodes in each list ≤ 50-100 ≤ Node.val ≤ 100Both input lists are sorted ascending
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.