Skip to main content

96. Merge k Sorted Lists

hardAsked at Workday

Merge k sorted linked lists into one sorted list. Workday uses this for heap composition — same shape as merging time-sorted payroll streams from k departments into one chronological ledger.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — direct payroll-merge analogy.

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. Collect all, sort, rebuild

Push all values into array; sort; build linked list.

Time
O(N log N)
Space
O(N)
// throws away the sortedness of each input list

Tradeoff: Same complexity as heap but wastes the per-list sortedness.

2. Divide and conquer merge

Pairwise merge. log k merge levels, each O(N).

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

Tradeoff: Pairwise merging halves the number of lists each round. log k rounds, each touching all N nodes. Heap is the alternative — same complexity.

Workday-specific tips

Workday accepts either D&C or min-heap. D&C is cleaner in JS (no built-in heap). State the complexity O(N log k) and contrast with the naive O(Nk) of sequential merges.

Common mistakes

  • Merging sequentially (list 0 with 1, result with 2, ...) — O(Nk) instead of O(N log k).
  • Forgetting the empty-lists guard.
  • Off-by-one in the pairwise step (skip last if odd k).

Follow-up questions

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

  • Heap-based variant with PriorityQueue.
  • Merge Two Sorted Lists (LC 21) — the primitive.
  • Smallest Range Covering 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 or heap?

Same complexity O(N log k). D&C is straightforward in JS without a heap library. Heap is more memory-efficient for very large k.

Why O(N log k)?

log k levels of merging. Each level touches every node once across all merges. Total: N * log k.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →