23. Merge k Sorted Lists

Merge k sorted linked lists into one sorted linked list and return it.

Keep the current head of every list in a min-heap. Pop the smallest, append it, and push its successor.

1function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
2  const heap = new PriorityQueue<ListNode>((a, b) => a.val - b.val);
3  for (const l of lists) if (l) heap.enqueue(l);
4  const dummy = new ListNode(0);
5  let tail = dummy;
6  while (!heap.isEmpty()) {
7    const node = heap.dequeue()!;
8    tail = tail.next = node;
9    if (node.next) heap.enqueue(node.next);
10  }
11  return dummy.next;
12}

heap (min first)

merged

null

Push the head of each list.

1 / 0

Space: play/pause · ←/→: step