Merge k Sorted Lists

Combine k sorted linked lists into one sorted list. The standard use of a min-heap to always pick the smallest of several candidates. Solve it below in Python or JavaScript, then read the walkthrough.

HardLinked List Divide and Conquer Heap (Priority Queue)Merge Sort Tournament Sort Asked at 135 companies incl. Google, Amazon, Meta

Problem

You're given an array lists of k singly linked lists. Each list is sorted in non-decreasing order. Merge them all into a single sorted linked list and return its head.

Any of the lists may be empty, and lists itself may be empty; in that case return an empty list (null / None).

In the examples, each linked list is written as an array of its values from head to tail.

Example 1

Input: lists = [[2, 6, 9], [1, 7], [3, 4, 10]]
Output: [1, 2, 3, 4, 6, 7, 9, 10]

All eight values, from all three lists, in sorted order.

Example 2

Input: lists = []
Output: []

There are no lists, so the result is empty.

Example 3

Input: lists = [[], [5]]
Output: [5]

Empty lists contribute nothing.

Constraints

0 ≤ k ≤ 10⁴
0 ≤ lists[i].length ≤ 500
-10⁴ ≤ node value ≤ 10⁴
Each list is sorted in non-decreasing order.
The total number of nodes is at most 10⁴.

Practice

Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Merge k Sorted Lists in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Merge k Sorted Lists

Pattern: Min-heap of list heads

Merging two sorted lists is easy: compare the two heads and take the smaller. With k lists the same idea holds, the next node in the output is always the smallest of the k current heads, but scanning k heads for every node is slow.

That "repeatedly take the smallest of a changing set" is exactly what a min-heap does. Put every non-empty head in the heap. Pop the smallest, append it to the output, and push its next node if it has one. The heap never holds more than k nodes, so each step costs O(log k) instead of O(k).

Approach 1: Collect all values and sort

Walk every list, put all values in an array, sort it, and build a new list. Simple, but it ignores the fact that the inputs are already sorted.

Time O(N log N) · Space O(N)

Approach 2: Merge lists one at a time, or in pairs

Merging each list into a running result costs O(N·k) because early nodes get re-walked on every merge. Merging in pairs instead (list 0 with 1, 2 with 3, and so on, then repeat) halves the number of lists each round, so every node is touched O(log k) times. That reaches the optimal bound without a heap.

Time O(N log k) · Space O(1) extra (iterative)

Approach 3: Min-heap of the current heads

Push (node.val, index, node) for every non-empty list into a min-heap. The index breaks ties so two nodes are never compared directly.
Create a dummy node and a tail pointer.
While the heap isn't empty: pop the smallest, link it after tail, advance tail, and push the popped node's next if there is one.
Return dummy.next.

N is the total number of nodes; each is pushed and popped once.

Time O(N log k) · Space O(k)

Approach	Time	Space
Collect all values and sort	O(N log N)	O(N)
Merge lists one at a time, or in pairs	O(N log k)	O(1) extra (iterative)
Min-heap of the current heads	O(N log k)	O(k)

Solution code

Try the practice editor first. Both solutions pass every test above.

Merge k Sorted Lists solution in Python

import heapq


def merge_sorted_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    tail.next = None
    return dummy.next

Merge k Sorted Lists solution in JavaScript

function mergeSortedLists(lists) {
  // Minimal binary min-heap of nodes keyed by val.
  const heap = [];
  const push = (node) => {
    heap.push(node);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p].val <= heap[i].val) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < heap.length && heap[l].val < heap[m].val) m = l;
        if (r < heap.length && heap[r].val < heap[m].val) m = r;
        if (m === i) break;
        [heap[m], heap[i]] = [heap[i], heap[m]];
        i = m;
      }
    }
    return top;
  };

  for (const node of lists) if (node) push(node);
  const dummy = new ListNode();
  let tail = dummy;
  while (heap.length) {
    const node = pop();
    tail.next = node;
    tail = node;
    if (node.next) push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Common mistakes

Pushing nodes onto a Python heap as `(val, node)`. When two values tie, Python tries to compare the nodes and raises a TypeError. Add a tie-breaking counter or index.
Pushing empty lists (`None` / `null`) into the heap at the start.
Merging every list into one growing result in sequence, which looks fine but costs O(N·k).
Forgetting the empty cases: `lists` with no entries, or every entry empty.

What interviewers look for

Start from the two-list merge everyone knows and say what goes wrong at k: finding the smallest head is O(k) each time. Then name the fix: a min-heap keyed by value turns that into O(log k). Interviewers want to hear both the complexity, O(N log k), and where the log k comes from.

It's worth mentioning divide-and-conquer pair merging as an alternative with the same bound. In JavaScript, which has no built-in heap, it's often the faster thing to write correctly, and saying so shows judgment.

Follow-up questions

How would you do this without a heap?

Merge in pairs: combine lists 0 and 1, 2 and 3, and so on, then repeat on the results. There are log k rounds and each round touches every node once, so the total is O(N log k).

What if the lists are huge files on disk instead of in memory?

This is an external merge. Keep one read buffer per file and a heap of the current front value from each buffer, refilling buffers as they drain. Memory is O(k × buffer size) no matter how big the files are.

What if you only need the first m values of the merged result?

Stop after m pops. The heap version then costs O(k + m log k), which can be far less than merging everything.

Companies that ask Merge k Sorted Lists

Merge k Sorted Lists is tagged by 135 companies in our interview dataset. The score shows how often it comes up at each company.

and 111 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Merge k Sorted Lists

HardLinked List Divide and Conquer Heap (Priority Queue)Merge Sort Tournament Sort Asked at 135 companies incl. Google, Amazon, Meta

Problem

You're given an array lists of k singly linked lists. Each list is sorted in non-decreasing order. Merge them all into a single sorted linked list and return its head.

Any of the lists may be empty, and lists itself may be empty; in that case return an empty list (null / None).

In the examples, each linked list is written as an array of its values from head to tail.

Example 1

Input: lists = [[2, 6, 9], [1, 7], [3, 4, 10]]
Output: [1, 2, 3, 4, 6, 7, 9, 10]

All eight values, from all three lists, in sorted order.

Example 2

Input: lists = []
Output: []

There are no lists, so the result is empty.

Example 3

Input: lists = [[], [5]]
Output: [5]

Empty lists contribute nothing.

Constraints

0 ≤ k ≤ 10⁴
0 ≤ lists[i].length ≤ 500
-10⁴ ≤ node value ≤ 10⁴
Each list is sorted in non-decreasing order.
The total number of nodes is at most 10⁴.

Practice

Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Merge k Sorted Lists in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Merge k Sorted Lists

Pattern: Min-heap of list heads

Approach 1: Collect all values and sort

Walk every list, put all values in an array, sort it, and build a new list. Simple, but it ignores the fact that the inputs are already sorted.

Time O(N log N) · Space O(N)

Approach 2: Merge lists one at a time, or in pairs

Time O(N log k) · Space O(1) extra (iterative)

Approach 3: Min-heap of the current heads

Push (node.val, index, node) for every non-empty list into a min-heap. The index breaks ties so two nodes are never compared directly.
Create a dummy node and a tail pointer.
While the heap isn't empty: pop the smallest, link it after tail, advance tail, and push the popped node's next if there is one.
Return dummy.next.

N is the total number of nodes; each is pushed and popped once.

Time O(N log k) · Space O(k)

Approach	Time	Space
Collect all values and sort	O(N log N)	O(N)
Merge lists one at a time, or in pairs	O(N log k)	O(1) extra (iterative)
Min-heap of the current heads	O(N log k)	O(k)

Solution code

Try the practice editor first. Both solutions pass every test above.

Merge k Sorted Lists solution in Python

import heapq


def merge_sorted_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    tail.next = None
    return dummy.next

Merge k Sorted Lists solution in JavaScript

function mergeSortedLists(lists) {
  // Minimal binary min-heap of nodes keyed by val.
  const heap = [];
  const push = (node) => {
    heap.push(node);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p].val <= heap[i].val) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < heap.length && heap[l].val < heap[m].val) m = l;
        if (r < heap.length && heap[r].val < heap[m].val) m = r;
        if (m === i) break;
        [heap[m], heap[i]] = [heap[i], heap[m]];
        i = m;
      }
    }
    return top;
  };

  for (const node of lists) if (node) push(node);
  const dummy = new ListNode();
  let tail = dummy;
  while (heap.length) {
    const node = pop();
    tail.next = node;
    tail = node;
    if (node.next) push(node.next);
  }
  tail.next = null;
  return dummy.next;
}

Common mistakes

Pushing nodes onto a Python heap as `(val, node)`. When two values tie, Python tries to compare the nodes and raises a TypeError. Add a tie-breaking counter or index.
Pushing empty lists (`None` / `null`) into the heap at the start.
Merging every list into one growing result in sequence, which looks fine but costs O(N·k).
Forgetting the empty cases: `lists` with no entries, or every entry empty.

What interviewers look for

Follow-up questions

How would you do this without a heap?

Merge in pairs: combine lists 0 and 1, 2 and 3, and so on, then repeat on the results. There are log k rounds and each round touches every node once, so the total is O(N log k).

What if the lists are huge files on disk instead of in memory?

What if you only need the first m values of the merged result?

Stop after m pops. The heap version then costs O(k + m log k), which can be far less than merging everything.

Companies that ask Merge k Sorted Lists

Merge k Sorted Lists is tagged by 135 companies in our interview dataset. The score shows how often it comes up at each company.

and 111 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Merge k Sorted Lists

Approach 1: Collect all values and sort

Approach 2: Merge lists one at a time, or in pairs

Approach 3: Min-heap of the current heads

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you do this without a heap?

What if the lists are huge files on disk instead of in memory?

What if you only need the first m values of the merged result?

Companies that ask Merge k Sorted Lists

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Merge k Sorted Lists

Approach 1: Collect all values and sort

Approach 2: Merge lists one at a time, or in pairs

Approach 3: Min-heap of the current heads

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you do this without a heap?

What if the lists are huge files on disk instead of in memory?

What if you only need the first m values of the merged result?

Companies that ask Merge k Sorted Lists

Practice next

Get live help in the real interview