Merge Two Sorted Lists
Part of Practice: Core Surgery
You are given the heads of two linked lists, each already sorted in ascending order. Splice them together into one sorted list — reusing the existing nodes rather than creating new ones — and return its head.
Either list may be empty. Each list holds at most 50 nodes, but the technique should be O(m + n) regardless.
Examples
- Input:
- list1 = [1, 2, 4], list2 = [1, 3, 4]
- Output:
- [1, 1, 2, 3, 4, 4]
- Input:
- list1 = [], list2 = []
- Output:
- []
- Input:
- list1 = [], list2 = [0]
- Output:
- [0]
When one list is empty, the merge is just the other list.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.