023. Merge k Sorted Lists

At a Glance

Topic: Linked List
Pattern: Analyze Pattern
Difficulty: Hard
LeetCode: 023

Problem Statement

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 linked 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 <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.

Approach & Solution Steps

Brute force — flatten values into an array, sort, rebuild a new list — O(n log n) time / O(n) space (loses original node reuse).
Better — repeatedly merge two lists in sequence (merge list1+list2, then +list3, …) — O(k · n) time in worst case; simple but hidden quadratic factor when lists are imbalanced.
Acceptable — divide-and-conquer pairwise merge of lists array — O(n log k) time / O(log k) recursion stack; no heap, friendlier in languages without container/heap.
Optimal — min-heap of size k holding current head per list — O(n log k) time / O(k) extra; typical interview pick for clarity and stable asymptotics on skewed inputs.

Optimal JS Solution

class MinHeap {
  constructor() {
    this.values = [];
  }
  push(node) {
    this.values.push(node);
    this.bubbleUp(this.values.length - 1);
  }
  pop() {
    const top = this.values[0];
    const last = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }
  get length() {
    return this.values.length;
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.values[parentIndex].val <= this.values[index].val) {
        break;
      }
      [this.values[parentIndex], this.values[index]] = [
        this.values[index],
        this.values[parentIndex],
      ];
      index = parentIndex;
    }
  }
  bubbleDown(index) {
    const length = this.values.length;
    while (true) {
      const leftIndex = index * 2 + 1;
      const rightIndex = index * 2 + 2;
      let smallest = index;
      if (
        leftIndex < length &&
        this.values[leftIndex].val < this.values[smallest].val
      ) {
        smallest = leftIndex;
      }
      if (
        rightIndex < length &&
        this.values[rightIndex].val < this.values[smallest].val
      ) {
        smallest = rightIndex;
      }
      if (smallest === index) {
        break;
      }
      [this.values[index], this.values[smallest]] = [
        this.values[smallest],
        this.values[index],
      ];
      index = smallest;
    }
  }
}

function mergeKLists(lists) {
  const minHeap = new MinHeap();
  for (const head of lists) {
    if (head !== null && head !== undefined) {
      minHeap.push(head);
    }
  }
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (minHeap.length > 0) {
    const smallest = minHeap.pop();
    tail.next = smallest;
    tail = smallest;
    if (smallest.next !== null) {
      minHeap.push(smallest.next);
    }
  }
  return dummy.next;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.