Merge k Sorted Lists

HardLinked ListLinked ListHeapDivide and Conquer

Problem

You are given an array containing the heads of k linked lists, each already sorted in non-decreasing order. Merge all of them into a single sorted list and return its head.

Example. The lists 1 -> 4 -> 5, 1 -> 3 -> 4, and 2 -> 6 merge into 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Key idea

Folding the lists together one pair at a time reuses the two-list merge idea but does it k-1 times, and each merge can touch nearly every node, so total work scales with both the list count and the node count, expensive as k grows.

Two better strategies avoid that. The first keeps a min-heap holding the current front node of every list; repeatedly remove the smallest, append it to the result, and push that list's next node in its place. Every node is pushed and popped once, at logarithmic cost in the number of lists, so total work stays proportional to node count times a much smaller factor. The second borrows from merge sort: pair up the lists and merge each pair, cutting the list count in half, and repeat until one list remains.

Solution

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

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

  let remaining = lists;
  while (remaining.length > 1) { // pair up and merge, halving the list count each round
    const merged: Array<ListNode | null> = [];
    for (let i = 0; i < remaining.length; i += 2) {
      const first = remaining[i];
      const second = i + 1 < remaining.length ? remaining[i + 1] : null; // odd one out merges with null
      merged.push(mergeTwoLists(first, second));
    }
    remaining = merged;
  }

  return remaining[0];
}

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;

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

  tail.next = list1 !== null ? list1 : list2; // remainder is already sorted, attach it as-is

  return dummy.next;
}

Complexity

  • Time: O(N log k) for either approach, where N is the total node count and k the number of lists. Each node participates in a logarithmic number of comparisons.
  • Space: O(k) for the heap; O(log k) recursion depth for divide and conquer. Neither counts the output.

Watch out for

  • Some entries in the input array may already be empty lists; skip these before pushing onto the heap or pairing lists.
  • A heap comparator must never be asked to compare against a node from an exhausted list.
  • Merging one list at a time into a growing result is correct but quadratic in k, worth avoiding deliberately.

Pattern

This generalizes the two-list merge to many lists using two recurring tools: a heap for picking the current global minimum, and divide-and-conquer pairwise merging, both of which reappear whenever multiple sorted sequences need combining.

Related questions