Skip to main content

89. Merge k Sorted Lists

hardAsked at Reddit

Merge k sorted linked lists into one sorted list. Reddit uses this to test heap-based merging — the exact shape used when merging hot/new/rising/controversial ranked streams into a single user feed.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit feed-ranking on-site canonical.
  • Blind (2025-12)— Reported as Reddit infra 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. Sequential pairwise merge

Merge first two; merge result with third; etc.

Time
O(N*k)
Space
O(1)
// Each merge is O(N); k merges => O(N*k).

Tradeoff: Quadratic in k.

2. Min-heap of head pointers (optimal)

Push all heads into a min-heap. Pop smallest; append to result; push popped's next if exists.

Time
O(N log k)
Space
O(k)
// JS lacks a built-in heap; sketch:
function mergeKLists(lists) {
  // Use a simple sorted-array heap (real impl uses binary heap)
  const heap = lists.filter(Boolean).slice();
  heap.sort((a, b) => a.val - b.val);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.length) {
    const node = heap.shift();
    tail.next = node;
    tail = node;
    if (node.next) {
      // Binary-insert (placeholder for heap push)
      let lo = 0, hi = heap.length;
      while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (heap[mid].val < node.next.val) lo = mid + 1;
        else hi = mid;
      }
      heap.splice(lo, 0, node.next);
    }
  }
  return dummy.next;
}

Tradeoff: O(N log k). Use a real binary heap in production (binary-array heap.push/pop in O(log k)).

Reddit-specific tips

Reddit interviewers want the heap-based merge. Bonus signal: connect to their actual ranked-feed merger — hot/new/rising streams arrive sorted by score; merging via heap is exactly the architecture.

Common mistakes

  • Filtering empty lists with .filter(Boolean) but missing the check (null entries crash).
  • Forgetting to push popped's next.
  • Using sequential pairwise merge.

Follow-up questions

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

  • Divide-and-conquer merge — same O(N log k) but no heap.
  • Merge k sorted arrays (not lists).
  • 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

Why log k and not log N?

Heap size = k at most; pushing/popping is O(log k). Total operations = N.

D&C vs. heap?

Same asymptotic; D&C does pairwise merges in log k rounds. Heap is more elegant for streaming.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →