Skip to main content

24. Merge k Sorted Lists

hardAsked at ByteDance

Merge k sorted linked lists into one sorted list — ByteDance uses it as a direct stand-in for merging k partitioned ranking streams into a single feed.

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

Problem

Given an array of k sorted linked lists, merge them into one sorted linked list and return its head. The total number of nodes across all lists may be large.

Constraints

  • 0 <= k <= 10^4
  • 0 <= total nodes <= 10^4
  • -10^4 <= Node.val <= 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. Flatten and sort

Push every value into an array, sort it, then rebuild a linked list.

Time
O(N log N)
Space
O(N)
// collect all values into an array, sort, then convert back into nodes

Tradeoff:

2. Min-heap of list heads

Push each list's head into a min-heap. Pop the smallest, attach it to the output, then push its next pointer.

Time
O(N log k)
Space
O(k)
function mergeKLists(lists) {
  const heap = [];
  const up = (i) => { while (i > 0) { const p = (i - 1) >> 1; if (heap[p].val > heap[i].val) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } else break; } };
  const down = (i) => { const n = heap.length; for (;;) { const l = i * 2 + 1, r = l + 1; let s = i; if (l < n && heap[l].val < heap[s].val) s = l; if (r < n && heap[r].val < heap[s].val) s = r; if (s === i) break; [heap[s], heap[i]] = [heap[i], heap[s]]; i = s; } };
  for (const head of lists) if (head) { heap.push(head); up(heap.length - 1); }
  const dummy = { val: 0, next: null };
  let cur = dummy;
  while (heap.length) {
    const node = heap[0];
    cur.next = node;
    cur = cur.next;
    if (node.next) { heap[0] = node.next; down(0); }
    else { const last = heap.pop(); if (heap.length) { heap[0] = last; down(0); } }
  }
  cur.next = null;
  return dummy.next;
}

Tradeoff:

ByteDance-specific tips

ByteDance interviewers grade explicit reasoning about why log-k merge wins at TikTok scale — exactly the multi-stream merge their ranking layer runs to produce a single ordered feed.

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

Practice these live with InterviewChamp.AI →