Merge k Sorted Lists
Part of Practice: Design & Hard Surgery
You are given an array lists containing the heads of k linked lists, each sorted in ascending order. Merge all of them into one sorted linked list and return its head.
The array may be empty, and individual lists may be empty. There can be up to 10^4 lists and up to 10^4 total nodes (n). The interesting part is doing better than merging the lists into the result one at a time.
Examples
- Input:
- lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
- Output:
- [1, 1, 2, 3, 4, 4, 5, 6]
All eight nodes from the three lists, in one sorted chain.
- Input:
- lists = []
- Output:
- []
- Input:
- lists = [[]]
- Output:
- []
One list that is itself empty merges to an empty list.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.