Merge k Sorted Lists

1. Define the problem

You are given an array of k linked lists, each sorted in ascending order. Merge all the lists into one sorted linked list and return its head. Pair up the lists and merge each pair with the same two pointer walk used to merge two sorted lists, then repeat on the results — halving the number of lists each pass, the same divide and conquer shape as merge sort.

Constraints

k == lists.length
0 ≤ k ≤ 10⁴
0 ≤ lists_i.length ≤ 500
-10⁴ ≤ lists_i[j] ≤ 10⁴

Example

Inputlists = [[1, 4, 5], [1, 3, 4], [2, 6]]

Output[1, 1, 2, 3, 4, 4, 5, 6]

Explanation Merging all three sorted lists produces one sorted list containing every value.

2. Know the words first

In plain terms

Divide and conquer: Break a problem into smaller pieces, solve each piece the same way, then combine the results.

3. Visualize the solution

Pair up lists, merge each pair, repeat until one list remains

L01,4,5

L11,3,4

L22,6

Statusinit

Three sorted lists to merge: [1, 4, 5], [1, 3, 4], [2, 6].

What happens in this step

heads = [L0, L1, L2] = [[1,4,5], [1,3,4], [2,6]]

mergeRange(heads, 0, 2): mid = floor((0+2)/2) = 1
  left  = mergeRange(heads, 0, 1)
  right = mergeRange(heads, 2, 2) = L2

The range still spans more than one list, so it recurses — the same halving shape as splitting an array in merge sort.

Step 1 of 5

Steps to visualize

Pair up the k lists and merge each pair with the standard two pointer merge — the same routine used to merge two sorted lists.
That halves the number of lists each pass, exactly like merge sort halves an array each level.
Repeat pairwise merging on the results until only one merged list remains.
The total work is O(N log k) — N nodes moved once per level, across log k levels.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Pair up lists, merge each pair, repeat until one list remains

L01,4,5

L11,3,4

L22,6

Statusinit

Three sorted lists to merge: [1, 4, 5], [1, 3, 4], [2, 6].

What happens in this step

heads = [L0, L1, L2] = [[1,4,5], [1,3,4], [2,6]]

mergeRange(heads, 0, 2): mid = floor((0+2)/2) = 1
  left  = mergeRange(heads, 0, 1)
  right = mergeRange(heads, 2, 2) = L2

The range still spans more than one list, so it recurses — the same halving shape as splitting an array in merge sort.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function mergeKLists(lists) {
  function buildList(arr) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    for (const v of arr) {
      curr.next = { val: v, next: null };
      curr = curr.next;
    }
    return dummy.next;
  }

  function toArray(head) {
    const result = [];
    let node = head;
    while (node) {
      result.push(node.val);
      node = node.next;
    }
    return result;
  }

  function mergeTwo(a, b) {
    const dummy = { val: 0, next: null };
    let tail = dummy;
    while (a && b) {
      if (a.val <= b.val) {
        tail.next = a;
        a = a.next;
      } else {
        tail.next = b;
        b = b.next;
      }
      tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
  }

  // divide and conquer over the k lists, just like splitting an array in merge sort
  function mergeRange(heads, start, end) {
    if (start > end) return null;
    if (start === end) return heads[start];

    const mid = Math.floor((start + end) / 2);
    const left = mergeRange(heads, start, mid);
    const right = mergeRange(heads, mid + 1, end);

    return mergeTwo(left, right);
  }

  const heads = lists.map(buildList);
  if (heads.length === 0) return [];

  return toArray(mergeRange(heads, 0, heads.length - 1));
}

Time: O(N log k)
Space: O(log k)

6. Test cases

Test cases

Input	Expected	Covers
`lists = [[1, 4, 5], [1, 3, 4], [2, 6]]`	`[1, 1, 2, 3, 4, 4, 5, 6]`	example from the docstring
`lists = []`	`[]`	no lists to merge at all
`lists = [[1, 2, 3]]`	`[1, 2, 3]`	only one list, already sorted
`lists = [[], [1]]`	`[1]`	one of the lists is empty
`lists = [[], [], []]`	`[]`	every list is empty
`lists = [[1, 3], [2, 4]]`	`[1, 2, 3, 4]`	boundary case, exactly two lists
`lists = [[1, 1], [1, 1]]`	`[1, 1, 1, 1]`	the same values repeated across lists
`lists = [[5], [1], [3], [2]]`	`[1, 2, 3, 5]`	an odd number of lists, each with a single node

Merge k Sorted Lists