Skip to main content

25. Merge k Sorted Lists

hardAsked at Squarespace

Merge k sorted linked lists into one sorted list; Squarespace uses it to test whether you reach for a min-heap or pairwise merge to beat the naive O(k*N) concatenation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of k sorted linked lists, merge all the lists into one sorted linked list and return its head.

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4

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
[]

Approaches

1. Collect, sort, rebuild

Drain all values into an array, sort it, then build a fresh linked list.

Time
O(N log N)
Space
O(N)
const a=[];
for(const l of lists){ let n=l; while(n){ a.push(n.val); n=n.next; } }
a.sort((x,y)=>x-y);
const dummy={next:null}; let cur=dummy;
for(const v of a){ cur.next={val:v,next:null}; cur=cur.next; }
return dummy.next;

Tradeoff:

2. Pairwise merge tree

Repeatedly merge pairs of lists until only one remains; each level processes every node once for log k levels total.

Time
O(N log k)
Space
O(1)
function mergeKLists(lists) {
  const mergeTwo = (a, b) => {
    const d = { next: null }; let c = d;
    while (a && b) { if (a.val <= b.val) { c.next = a; a = a.next; } else { c.next = b; b = b.next; } c = c.next; }
    c.next = a || b;
    return d.next;
  };
  let arr = lists.slice();
  if (!arr.length) return null;
  while (arr.length > 1) {
    const next = [];
    for (let i = 0; i < arr.length; i += 2) next.push(mergeTwo(arr[i], arr[i + 1] || null));
    arr = next;
  }
  return arr[0];
}

Tradeoff:

Squarespace-specific tips

Squarespace likes when you connect this k-way merge to their analytics rollup, which merges per-site per-minute time-series shards into a single hourly stream for the dashboard.

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 Squarespace interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →