In LeetCode 23: Merge K Sorted Lists, we are given an array of k singly linked list heads, where each linked list is already sorted in ascending order. Our objective is to merge all k lists into a single sorted linked list in optimal O(N log k) time, where N is the total number of nodes across all lists.

Problem Statement and Examples

This problem models external k-way merge sort used by LSM-tree storage engines (such as RocksDB and LevelDB SSTable compaction) and distributed log aggregators that interleave time-ordered event streams.

Example 1: Merging Three Sorted Lists

Input:  lists = [[1 -> 4 -> 5], [1 -> 3 -> 4], [2 -> 6]]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Explanation:
At each step we select the smallest head across the three active lists and advance its pointer.

Example 2: Empty Input and Empty Sublists

Input:  lists = []        -> Output: []
Input:  lists = [[]]      -> Output: []

Constraints

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• The sum of lists[i].length across all lists does not exceed 10^4.
• -10^4 <= Node.val <= 10^4

Approach 1: Min-Heap / Priority Queue (O(N log k) Time, O(k) Space)

If we scanned all k list heads linearly to pick the minimum node at each step, merging N nodes would take O(N * k) time. Instead, we maintain a min-heap (priority queue) of size at most k that holds only the current head pointer of each non-empty list:

1. Initialization: Push the non-null head of each of the k lists into the min-heap. Building or inserting up to k elements takes O(k log k) time.
2. Extract-Min and Advance: Pop the node with the smallest value from the min-heap in O(log k) time and append it to the merged tail pointer. If the extracted node has a non-null next pointer, push node->next into the min-heap in O(log k) time.
3. Termination: Once the min-heap is empty, return dummy.next.

C++20 Min-Heap Implementation

Notice that we allocate the sentinel dummy node on the stack rather than with new to prevent a heap memory leak:

#include <iostream>
#include <queue>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    explicit ListNode(int x = 0, ListNode* n = nullptr) : val(x), next(n) {}
};

struct MinNodeCompare {
    bool operator()(const ListNode* a, const ListNode* b) const noexcept {
        return a->val > b->val; // Smallest value has highest priority
    }
};

ListNode* mergeKListsHeap(const std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, MinNodeCompare> minHeap;

    for (ListNode* head : lists) {
        if (head != nullptr) {
            minHeap.push(head);
        }
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop();

        tail->next = smallest;
        tail = tail->next;

        if (smallest->next != nullptr) {
            minHeap.push(smallest->next);
        }
    }

    return dummy.next;
}

Approach 2: Iterative Divide and Conquer (O(N log k) Time, O(1) Space)

Can we achieve the exact same O(N log k) time complexity while reducing auxiliary space from O(k) to O(1)? Yes—by applying bottom-up divide and conquer pairwise merging:

• In Round 1, we merge list pairs (0, 1), (2, 3), (4, 5), ..., halving the number of lists from k to ceil(k / 2) while doing O(N) total pointer splices.
• In Round 2, we merge pairs at stride 2, reducing the active lists to ceil(k / 4).
• After ceil(log2 k) rounds, all lists are coalesced into lists[0] using zero heap allocations.

TypeScript Iterative Divide-and-Conquer Implementation

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoSortedLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }

  tail.next = l1 !== null ? l1 : l2;
  return dummy.next;
}

export function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const k = lists.length;
  if (k === 0) return null;

  for (let interval = 1; interval < k; interval *= 2) {
    for (let i = 0; i + interval < k; i += interval * 2) {
      lists[i] = mergeTwoSortedLists(lists[i], lists[i + interval]);
    }
  }

  return lists[0];
}

Architectural Trade-Offs and Complexity Comparison