30. Merge K Sorted Lists

hardAsked at Spotify

Merge k sorted linked lists into one sorted list — a priority-queue pattern that maps to how Spotify merges sorted event streams from multiple data-pipeline shards when reconstructing a global play-history timeline.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

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 it.

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
Total nodes <= 10^4
-10^4 <= lists[i][j].val <= 10^4
Each list is sorted in non-decreasing order

Examples

Example 1

Input

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

Output

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

Example 2

Input

lists = []

Output

[]

Example 3

Input

lists = [[]]

Output

[]

Approaches

1. Brute force — collect and sort

Traverse all lists, collect all values into an array, sort, then rebuild a linked list. Simple but ignores the sorted property of input lists.

Time: O(N log N) where N = total nodes
Space: O(N)

function mergeKLists(lists) {
  const vals = [];
  for (let list of lists) {
    while (list) { vals.push(list.val); list = list.next; }
  }
  vals.sort((a, b) => a - b);
  const dummy = { val: 0, next: null };
  let cur = dummy;
  for (const v of vals) { cur.next = { val: v, next: null }; cur = cur.next; }
  return dummy.next;
}

Tradeoff:

2. Divide and conquer (optimal)

Pair up lists and merge each pair using the merge-two-sorted-lists subroutine; repeat until one list remains. O(N log k) — the same divide-and-conquer approach used in external merge sort for multi-shard logs.

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

function mergeKLists(lists) {
  const mergeTwoLists = (l1, l2) => {
    const dummy = { val: 0, next: null };
    let cur = dummy;
    while (l1 && l2) {
      if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
      else { cur.next = l2; l2 = l2.next; }
      cur = cur.next;
    }
    cur.next = l1 || l2;
    return dummy.next;
  };
  if (!lists.length) return null;
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

Tradeoff:

Spotify-specific tips

Spotify's data infrastructure team runs this exact algorithm under the hood when merging sorted partition outputs from distributed streaming jobs. Interviewers want you to recognise that pairing lists and halving the problem each round is equivalent to a merge-sort tree — the O(N log k) complexity should feel intuitive, not memorised. Walk through a 4-list example to show you can trace the pairing rounds.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Merge K Sorted Lists and other Spotify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →