[Leetcode] Merge k Sorted Lists

An extension of Merge Two Sorted Lists. Use heap to keep next pair (val, index) at the top. Shift head to next of target list for directly getting target node in future round.

Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Examples

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Solution

To merge multiple lists, in each round of loop, we have to know the curr min node of all lists. As lists are sorted, we can conveniently get the min node in one list. Put these together then the min of min can be known. Since only min is being questioned, use a heap to avoid sorting every node.

When the min of min is popped, the heap shall push another node from the list same with the popped. To do so, elms in heap contain not only val of node but the list index where the node is from. When heap pops the top, use the index to find the list so the heap can push new elms of same list, ensuring one node per list.

To form the linked list to return, each node is initiated by using the val and the curr variable shifts its position to the new node. For the list of new node, similarily shift its head to next, so when next time the list is called it directly returns smallest unused node.

• code

ref: https://zhenyu0519.github.io/2020/07/09/lc23/