Skip to main content

23. Merge K Sorted Lists

hardAsked at Juniper Networks

Merge k sorted linked lists into one sorted list efficiently. Juniper's control plane regularly merges sorted streams from multiple routing protocol tables (OSPF, BGP, IS-IS) into a unified RIB — a k-way merge with a min-heap is the production algorithm behind this operation.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2026-Q1)— Cited in Juniper SWE onsite reports as a high-difficulty problem in routing and platform team interviews.
  • Blind (2025-12)— Juniper interview threads list Merge K Sorted Lists as the canonical hard linked-list problem with direct networking relevance.

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]

Explanation: Three sorted lists merged into one.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input.

Example 3

Input
lists = [[]]
Output
[]

Explanation: Single empty list.

Approaches

1. Divide and conquer (pair-wise merges)

Reduce k lists to 1 by repeatedly merging pairs. Each pass halves the number of lists. Uses the O(m+n) two-list merge as a primitive.

Time
O(N log k) where N = total nodes
Space
O(log k) call stack
function mergeTwoLists(l1, l2) {
  const dummy = { next: null };
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}
function mergeKLists(lists) {
  if (!lists || lists.length === 0) 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: O(N log k) time, O(1) extra space (excluding output). The divide-and-conquer insight: each node participates in O(log k) merges, giving the log k factor.

2. Min-heap — direct k-way merge

Use a min-heap (priority queue) seeded with the first node of each list. Repeatedly extract the minimum, append to result, and push the next node from the same list.

Time
O(N log k)
Space
O(k) heap
// JavaScript lacks a built-in heap; simulate with a sorted structure
// In a real interview, implement a MinHeap or use a language with PriorityQueue
function mergeKLists(lists) {
  // Simulated via sorted array insertion (interview pseudocode)
  // Production: use a proper MinHeap with O(log k) push/pop
  const heap = [];
  const push = (node) => {
    if (!node) return;
    heap.push(node);
    heap.sort((a, b) => a.val - b.val); // O(k log k) per op — use real heap in prod
  };
  for (const head of lists) push(head);
  const dummy = { next: null };
  let curr = dummy;
  while (heap.length) {
    const node = heap.shift();
    curr.next = node;
    curr = curr.next;
    push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) with a real min-heap. In JavaScript, implement a binary heap class or note that the sort simulation is for illustration only. The min-heap is the canonical approach in most languages with built-in priority queues (Java PriorityQueue, Python heapq, C++ std::priority_queue).

Juniper Networks-specific tips

Lead with the divide-and-conquer approach in JavaScript since a built-in heap is not available. In a Juniper interview, mention both approaches and their space tradeoffs: divide-and-conquer uses O(log k) stack space while the heap uses O(k). The O(N log k) time complexity derivation is worth explaining: N total nodes, each participating in O(log k) merge rounds. Connect directly to networking: 'Junos merges route streams from OSPF areas, BGP peers, and static routes into a unified RIB — this is a k-way merge.'

Common mistakes

  • Using a sequential merge (merge list 0 with 1, result with 2, etc.) — O(kN) time, not O(N log k).
  • Not handling empty lists or null heads in the heap — push(node.next) can push null.
  • Forgetting the k=0 and k=1 edge cases.
  • Not disconnecting curr.next before returning — left-over next pointers from original lists can corrupt the result.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Sort a Linked List (LC 148) — merge sort applied to a single linked list.
  • Find K-th Smallest Element Across K Sorted Arrays — same heap approach applied to arrays.
  • How would you handle merging k sorted streams in a distributed system where each stream arrives from a different routing protocol daemon?

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 is the naive sequential merge O(kN) not O(N log k)?

Merging lists one at a time means the first list participates in k-1 merge rounds. Its N/k nodes are each touched O(k) times. Total cost = sum over k rounds = O(kN) in the worst case.

How does divide-and-conquer achieve O(N log k)?

After sorting, each node participates in exactly log k merge rounds (the number of pairing levels). Total cost = N nodes * log k rounds = O(N log k).

When would you prefer the heap over divide-and-conquer?

When the k lists arrive incrementally (streaming) and you cannot store all list heads up front. The heap naturally processes nodes in a streaming fashion.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →