Merge multiple sorted singly linked lists into one sorted linked list.
You are given an array of singly linked lists, where each list is already sorted in non-decreasing order.
Merge all of the lists into one sorted linked list and return the head of the merged list.
Your solution should reuse existing nodes when possible and produce a single sorted chain containing every node from the input lists exactly once.
Input Format
- An array of linked-list heads.
- Each linked list contains integer values in non-decreasing order.
- Some lists may be empty.
Output Format
- Return the head of one merged linked list in non-decreasing order.
Constraints
- The total number of nodes across all lists is finite.
- Input lists are individually sorted in non-decreasing order.
- If all lists are empty, return an empty list.
Example 1
Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
Explanation
Take the smallest available node from the heads of the lists until all nodes are merged into one sorted list.
Example 2
Input
lists = []
Output
[]
Explanation
There are no lists to merge, so the result is empty.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.