You are given a list of k linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.
Merging two lists at a time is O(kN) overall. The classic approach keeps the current front node of every list in a min-heap: pop the smallest, append it to the result, and push that list's next node. Each node passes through the heap once, giving O(N log k).
Examples
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Input: lists = []
Output: []
Input: lists = [[]]
Output: []
Constraints
0 <= k <= 100- Each list has at most 500 nodes, sorted ascending; some lists may be empty.
Goals
- Perform a k-way merge with a heap holding one candidate per list
- Add a tie-breaker to heap tuples so non-comparable objects are never compared
- Build a linked list with a dummy head and tail pointer