Merge k Sorted Lists

You are given an array lists of k singly linked lists. Each list is sorted in non-decreasing order.

Merge all of them into a single sorted linked list and return its head. You may reuse the existing nodes. If there are no lists, or every list is empty, return an empty list.

In the tests each linked list is written as an array of its values, so [[2, 5, 9], [1, 6]] means two lists, 2→5→9 and 1→6.

Example 1

Example 2

Example 3

Constraints

• 0 <= k == lists.length <= 104
• 0 <= length of each list <= 500
• -104 <= Node.val <= 104
• Each list is sorted in non-decreasing order.
• The total number of nodes is at most 104.

Pattern Path · Linked Lists · problem 78 of 169

Start simple

Copy every value into an array, sort it and build a new list: O(N log N) time and O(N) extra space; folding the lists in one by one is O(N · k).

The key idea

Merging two sorted lists is easy: repeatedly take the smaller head. The question is how to combine k lists without doing too much repeated work. Let N be the total number of nodes.

Merging the lists one after another into a growing result is slow: the result is walked again for every new list, giving O(N · k).

Instead, merge in rounds, like merge sort. Pair up the lists and merge each pair, which leaves about k/2 lists. Repeat until one list remains. Each round touches every node once, which is O(N), and the number of lists halves every round, so there are only log k rounds. Total: O(N log k), using only the simple two-list merge.

An equally good alternative is a min-heap holding the current head of every list: pop the smallest node, append it to the result, and push its successor. The heap never holds more than k nodes, so each of the N steps costs O(log k), the same bound.

Complexity

• Time: O(N log k), N = total nodes
• Space: O(k) for the list of merged heads (O(1) extra per merge)

Python

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        # Merge neighbours in rounds: k lists -> k/2 -> k/4 -> ... -> 1.
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                second = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(self.mergeTwo(lists[i], second))
            lists = merged
        return lists[0]

    def mergeTwo(self, a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()
        while a and 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 or b   # append whatever is left
        return dummy.next

JavaScript

var mergeKLists = function(lists) {
  if (lists.length === 0) return null;
  // Merge neighbours in rounds: k lists -> k/2 -> k/4 -> ... -> 1.
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const second = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwo(lists[i], second));
    }
    lists = merged;
  }
  return lists[0];
};

function mergeTwo(a, b) {
  const dummy = new ListNode();
  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;   // append whatever is left
  return dummy.next;
}

What the interviewer is checking

The interviewer wants to see you go beyond the obvious fold, explain why it is O(N · k), and bring it down to O(N log k) with divide-and-conquer or a heap.

Mistakes to avoid

• Not handling an empty lists array or lists that are empty (null).
• Folding lists one by one into the result, which is O(N · k) and times out for many lists.
• In Python, pushing ListNode objects into heapq directly: equal values make it compare nodes and raise an error. Add a tie-breaker index.

Follow-ups to expect

• Implement it with a min-heap instead. (Store (value, index, node) tuples.)
• What if the lists are huge files on disk? (External k-way merge with buffers.)
• Merge k sorted arrays and return the k-th smallest overall. (Heap, stop after k pops.)

In real software

Databases and search engines merge many sorted runs or posting lists into one (the merge step of external sort, LSM-tree compaction), which is exactly a k-way merge.

Practice next