27. Merge K Sorted Lists

hardAsked at Unity

Merge k sorted linked lists into one sorted list — the same k-way merge Unity's profiler uses when combining per-thread frame-timing streams into a single sorted timeline before rendering the CPU usage graph.

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 linked 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].val <= 10^4
Total nodes across all lists <= 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. Brute force — collect and sort

Flatten all list values into an array, sort, rebuild as a linked list. Simple but O(N log N) with extra space.

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

function mergeKLists(lists) {
  const vals = [];
  for (let node of lists) {
    while (node) { vals.push(node.val); node = node.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 pairwise merge

Repeatedly pair lists and merge each pair. Each pass halves the list count. Total work is O(N log k) — the same merge-sort decomposition applied to linked lists.

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

function mergeKLists(lists) {
  function mergeTwoLists(a, b) {
    const dummy = { val: 0, next: null };
    let cur = dummy;
    while (a && b) {
      if (a.val <= b.val) { cur.next = a; a = a.next; }
      else { cur.next = b; b = b.next; }
      cur = cur.next;
    }
    cur.next = a || b;
    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:

Unity-specific tips

Unity's profiler team deals with exactly this problem. Lead with the divide-and-conquer approach and name O(N log k) explicitly — interviewers will ask you to justify the log k factor by tracing through how many merge passes occur. Bonus: mention that a min-heap alternative achieves the same complexity but with O(k) extra space for the heap.

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

Practice these live with InterviewChamp.AI →