72. Merge K Sorted Lists
Merge all supplied sorted lists into a single nondecreasing list. Empty input lists contribute no nodes, and every original node must appear exactly once.
Relink the original nodes rather than copying them. Follow the contract's deterministic ordering for equal values from different source lists.
Example 1
Input
L0:[1,4,5], L1:[1,3,4], L2:[2,6]
Output
L0:0,L1:0,L2:0,L1:1,L0:1,L1:2,L0:2,L2:1
Explanation: The first 1 tie favors source 0; the 4 tie also favors source 0. Every label is an original object.
Example 2
Input
L0:[2,2], L1:[2,2]
Output
L0:0,L0:1,L1:0,L1:1
Explanation: After extracting L0:0, its equal-valued successor still outranks every source-1 tie.
Example 3
Input
[null,null]
Output
null
Explanation: No source frontier exists and the dummy is not returned.
Constraints
0 <= lists.length <= 1040 <= total node count <= 105-231 <= node.value <= 231 - 1- Source lists are sorted, acyclic and node-disjoint.
Hints
Hint 1
What is the smallest unconsumed candidate from each sorted source?
Hint 2
Put only those candidates into a min-heap with source-index ties.
Hint 3
Poll, save the original successor, append the exact node, and offer only that source’s successor.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Advance only the extracted source
[[1,4,5],[1,3,4],[2,6]]
["L0:0","L1:0","L2:0","L1:1","L0:1","L1:2","L0:2","L2:1"]