Skip to main content

97. Merge k Sorted Lists

hardAsked at Ola

Merge k sorted linked lists into one sorted list.

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

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
  • Sum of lengths <= 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 then sort

Drop all values into one array, sort, rebuild a linked list.

Time
O(N log N)
Space
O(N)
const arr = []; for (const l of lists) { let n=l; while(n){arr.push(n.val); n=n.next;} }
arr.sort((a,b)=>a-b);
const dummy = {next:null}; let t=dummy;
for (const v of arr){ t.next = {val:v,next:null}; t = t.next; }
return dummy.next;

Tradeoff:

2. Divide and conquer pairwise merge

Repeatedly merge pairs of lists until one remains; each level is O(N), with log k levels.

Time
O(N log k)
Space
O(1)
function mergeKLists(lists) {
  const mergeTwo = (a, b) => {
    const dummy = { next: null }; let t = dummy;
    while (a && b) {
      if (a.val <= b.val) { t.next = a; a = a.next; }
      else { t.next = b; b = b.next; }
      t = t.next;
    }
    t.next = a || b;
    return dummy.next;
  };
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) merged.push(mergeTwo(lists[i], lists[i+1] || null));
    lists = merged;
  }
  return lists[0] || null;
}

Tradeoff:

Ola-specific tips

Ola engineers value the divide-and-conquer pattern; tie it to merging per-region driver-supply streams into one global sorted 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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →