Merge k Sorted Lists

Problem

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.

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: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won't exceed 10^4.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const minHeap = new MinPriorityQueue({ priority: node => node.val });

    // add front node of each list to heap
    for (const node of lists) {
        if (node) {
            minHeap.enqueue(node);
        }
    }

    // merge all lists
    const dummy = new ListNode();
    cur = dummy;
    while (!minHeap.isEmpty()) {
        cur.next = minHeap.dequeue().element;
        cur = cur.next;
        if (cur.next) {
            minHeap.enqueue(cur.next);
        }
    }
    return dummy.next;
};

We will use a min-heap minHeap to store the node with the smallest value for each of the k linked lists (ie. one node for each of the k lists). We initialize minHeap with the first element of each list. Next, we continuously get the top node from minHeap, appended it to the end of our new linked list, and add the next node of that list into minHeap (provided there are more nodes).

Problem​

Solution​

Problem

Solution