Skip to main content

97. Merge k Sorted Lists

hardAsked at Vercel

Merge k sorted linked lists into one. Vercel asks this constantly — they literally merge k sorted log streams from edge POPs in their analytics pipeline, and the heap-based merge is the production solution.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel analytics-team onsite; literally their problem.
  • Blind (2026-Q1)— Reported as the canonical Vercel data-plane hard.

Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 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. Naive sequential merge

Merge list[0] with list[1], then with list[2], etc.

Time
O(N * k)
Space
O(1)
// O(N*k) where N is total nodes. Worse than divide-and-conquer.

Tradeoff: Quadratic in k.

2. Divide-and-conquer pairwise merge (optimal)

Pair up lists; merge each pair; repeat until one list remains.

Time
O(N log k)
Space
O(log k) recursion
function mergeKLists(lists) {
  if (!lists.length) return null;
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const a = lists[i], b = lists[i + 1] || null;
      merged.push(mergeTwo(a, b));
    }
    lists = merged;
  }
  return lists[0];
}
function mergeTwo(a, b) {
  const dummy = { 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;
}

Tradeoff: O(N log k) by tournament-style merging. Min-heap approach is similar complexity; D&C avoids the heap library.

Vercel-specific tips

Vercel grades EITHER divide-and-conquer OR min-heap. Bonus signal: discussing both and picking based on memory constraints (heap uses O(k) memory; D&C uses recursion stack of O(log k)). Mention that the heap variant is more streaming-friendly.

Common mistakes

  • Sequential merge (one at a time) — O(N*k) instead of O(N log k).
  • Forgetting null lists in the input — must filter or handle in mergeTwo.
  • Using shift() on the list array — O(n) per shift.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Streaming variant — merge as lists grow.
  • Merge k sorted arrays (not linked lists).
  • Smallest range covering elements from k lists (LC 632).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

D&C vs min-heap?

Both are O(N log k). D&C is simpler in JS (no heap library), uses O(log k) recursion stack. Min-heap uses O(k) memory but is more streaming-friendly (can process new nodes as they arrive).

Why O(N log k)?

Each round halves the number of lists; there are log k rounds. Each round processes N total nodes (sum across all merges). Total: N * log k.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →