Merge k Sorted Lists

Q: Why does the Python heap need the index in each tuple?

When two heads have equal values, heapq compares the next tuple element. Without the index it would compare two ListNode objects, which do not define <, and crash. The index is unique, so the comparison never reaches the node.

Q: Why is this relevant for infrastructure roles?

It is the k-way merge behind combining sorted log files from many hosts into one timeline, merging sorted shards of a large sort, or collating time series from several sources. Tools that tail logs from many pods do the same thing with a heap keyed on timestamp.

hardHeaps and top-K

You are given an array of k singly linked lists. Each list is already sorted in non-decreasing order, and any of them may be empty. Combine all their nodes into one linked list that is also sorted in non-decreasing order, and return its head.

If there are no nodes at all, return an empty list (None / null).

Examples

Example 1

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

Output: [1, 2, 3, 4, 6, 6, 9, 10]

Example 2

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

Output: [5]

Explanation: Empty lists contribute nothing.

Hints

Approach

At any moment the next node of the output is the smallest of the current heads of the k lists. A min-heap keyed on node value returns that smallest head in O(log k).

Push the head of every non-empty list into a min-heap.
Pop the smallest node and attach it to the tail of the result.
If that node has a next, push it. The heap never holds more than k nodes.
Repeat until the heap is empty.

In Python, heap entries are (value, index, node) tuples. The unique index breaks ties so Python never has to compare two ListNode objects, which would raise a TypeError. The existing nodes are relinked, not copied.

ComplexityTime O(N log k)Space O(k) for the heap

Python

import heapq
 
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: list["ListNode | None"]) -> "ListNode | None":
        heap = []
        for i, node in enumerate(lists):
            if node:
                heap.append((node.val, i, node))
        heapq.heapify(heap)
        dummy = tail = ListNode(0)
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Follow-up questions

The inputs are k sorted files too large to fit in memory. How do you merge them into one sorted file?
Merge sorted log streams by timestamp where each stream is a generator, not a list.

Frequently asked questions

Yes: divide and conquer. Merge the lists in pairs with the two-list merge, then merge the results in pairs, and so on. There are log k rounds and each round touches every node once, so it is also O(N log k), with O(1) extra space if done iteratively. Merging the lists one after another into a growing result is simpler but costs O(N · k).

When two heads have equal values, heapq compares the next tuple element. Without the index it would compare two ListNode objects, which do not define <, and crash. The index is unique, so the comparison never reaches the node.

It is the k-way merge behind combining sorted log files from many hosts into one timeline, merging sorted shards of a large sort, or collating time series from several sources. Tools that tail logs from many pods do the same thing with a heap keyed on timestamp.

Problem statement