Merge K Sorted Lists

Examples

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

The array contains one list, and that list happens to be empty.

Constraints

• 0 <= k <= 10^4

• 0 <= length of each list <= 500

• The total number of nodes across all lists is at most 10^4.

• Each individual list is sorted in non-decreasing order.

Approach

The most direct approach ignores that the lists are already sorted: dump every value from every list into one array, sort that array, then rebuild a single list from it.

A better approach reuses the two-list merge you'd use for merging just two sorted lists: merge the first list with the second, merge that result with the third, then with the fourth, and so on. This is simple and avoids a full sort, but the growing "result so far" list gets re-scanned by every subsequent merge, so the total work scales with both the number of lists and the total number of nodes.

The efficient approach merges the lists in pairs instead of one at a time: round 1 merges list 1 with list 2, list 3 with list 4, and so on, roughly halving the number of lists. Repeating this pairwise merging process on the results, round after round, brings the number of lists down to one in only about log2(k) rounds, and every node is only ever part of a two-list merge at each round, rather than being re-scanned by every single merge along the way.

Solutions

Brute Force — Collect All Values, Sort, Rebuild

Walk every list, pushing every value into one flat array. Sort that array, then build a brand-new list from the sorted values. This works regardless of how the input lists were ordered, but it pays for a full sort even though most of the ordering information was already there for free.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  const values = [];

  for (const list of lists) {
    let node = list;
    while (node) {
      values.push(node.val);
      node = node.next;
    }
  }

  values.sort((a, b) => a - b);

  const dummy = new ListNode(0);
  let curr = dummy;
  for (const value of values) {
    curr.next = new ListNode(value);
    curr = curr.next;
  }

  return dummy.next;
}

Time: O(N log N), where N is the total number of nodes across all lists · Space: O(N)

Sequential Merge — Fold Lists One at a Time

Reuse a standard two-list merge as a building block. Start with an empty running result, then merge in each list one after another: merge the result with list 1, then merge that with list 2, then with list 3, and so on until every list has been folded in.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (a !== null && b !== null) {
    if (a.val <= b.val) {
      curr.next = a;
      a = a.next;
    } else {
      curr.next = b;
      b = b.next;
    }
    curr = curr.next;
  }

  curr.next = a !== null ? a : b;
  return dummy.next;
}

function mergeKLists(lists) {
  let result = null;
  for (const list of lists) {
    result = mergeTwoLists(result, list);
  }
  return result;
}

Time: O(k * N), where k is the number of lists and N is the total number of nodes · Space: O(1) extra, reusing existing nodes

Optimal — Pairwise (Divide and Conquer) Merge

Reuse the same two-list merge, but instead of folding lists in one at a time, merge them in pairs each round: list 1 with list 2, list 3 with list 4, and so on, producing roughly half as many lists as before. Repeat this pairing process on the new, smaller collection of lists, again and again, until only one list remains.

Because the number of lists roughly halves every round, it only takes about log2(k) rounds to finish, and each round does a total of O(N) work across all its merges (every node is touched exactly once per round), giving O(N log k) overall instead of O(N * k).

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  let curr = dummy;

  while (a !== null && b !== null) {
    if (a.val <= b.val) {
      curr.next = a;
      a = a.next;
    } else {
      curr.next = b;
      b = b.next;
    }
    curr = curr.next;
  }

  curr.next = a !== null ? a : b;
  return dummy.next;
}

function mergeKLists(lists) {
  if (lists.length === 0) return null;

  let remaining = lists;
  while (remaining.length > 1) {
    const merged = [];

    for (let i = 0; i < remaining.length; i += 2) {
      const first = remaining[i];
      const second = i + 1 < remaining.length ? remaining[i + 1] : null;
      merged.push(mergeTwoLists(first, second));
    }

    remaining = merged;
  }

  return remaining[0];
}

Time: O(N log k), where N is the total number of nodes and k is the number of lists · Space: O(k) for the array of intermediate list heads (O(1) beyond that, reusing existing nodes)