Merge K Sorted Lists: Min Heap Merge

Merge K Sorted Lists is LeetCode 23, rated hard, and one of the most classic heap problems you will see in interviews. You are given k sorted linked lists and need to merge them into a single sorted linked list. If you already know how to merge two sorted lists, this problem asks: how do you scale that to k?

The brute force approach of merging lists one at a time works but is slow. The optimal solution uses a min heap to always pick the smallest head across all k lists, giving you O(n log k) time. There is also a divide-and-conquer approach that matches the same complexity by recursively merging pairs.

The problem

You are given an array of k linked lists, each sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Example: lists = [[1,4,5], [1,3,4], [2,6]]

The merged result should be [1, 1, 2, 3, 4, 4, 5, 6].

Why a min heap is perfect here

Think about what you need at each step: you have k list heads, and you want the smallest one. That is exactly what a min heap does. It gives you the minimum in O(1) and lets you insert a new element in O(log k).

The algorithm:

1. Push the head node of each non-empty list into a min heap.
2. Pop the minimum from the heap. Append it to the result.
3. If that node has a next pointer, push the next node into the heap.
4. Repeat until the heap is empty.

At any point, the heap holds at most k nodes (one from each list). Each of the n total nodes gets pushed and popped exactly once, giving you O(n log k) total work.

Visual walkthrough

Let's trace through merging [1,4,5], [1,3,4], and [2,6]. Watch how the heap always surfaces the global minimum.

The key observation: even though we have three separate lists, the heap always knows the global minimum. We never have to scan all k heads manually. The heap does that bookkeeping for us in O(log k) per operation.

Approach 1: Min heap

Here is the clean Python solution using heapq. Since Python's heap compares tuples lexicographically, we store (node_value, list_index, node) to break ties. The list index prevents comparison errors when two nodes have the same value.

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Let's break it down:

• Initialization. Push the head of each non-empty list. The tuple (val, i, node) lets Python compare by value first, then by list index to break ties.
• Main loop. Pop the smallest node, wire it into the result, and push its successor if one exists. The heap never holds more than k elements.
• Dummy head. The sentinel node avoids special-casing the first insertion. We return dummy.next at the end.

Time: O(n log k) where n is the total number of nodes across all lists. Each node is pushed and popped once, and each heap operation costs O(log k).

Space: O(k) for the heap, plus O(1) extra since we reuse the existing nodes.

Approach 2: Divide and conquer

Instead of a heap, you can merge lists in pairs, like a tournament bracket. Merge list 0 with list 1, merge list 2 with list 3, and so on. Then merge the results in pairs again. Each round halves the number of lists, and there are O(log k) rounds.

Each round processes all n nodes (across the remaining lists), so the total work is O(n log k). Same complexity, different style.

def merge_k_lists_dc(lists: list[ListNode | None]) -> ListNode | None:
    if not lists:
        return None

    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged

    return lists[0]

def merge_two(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
    dummy = ListNode(0)
    curr = dummy

    while l1 and 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 if l1 else l2
    return dummy.next

The merge_two function is the standard merge from Merge Sorted Array, just adapted for linked lists. The outer loop repeatedly pairs up lists and merges them until only one remains.

Time: O(n log k). There are O(log k) rounds, and each round does O(n) total work.

Space: O(1) extra (ignoring the merged list of pointers). We reuse the existing nodes without creating new ones. The recursion-free iterative approach avoids stack overhead.

Heap vs divide and conquer

Both are equally valid for interviews. The heap approach is more elegant and shorter. The divide-and-conquer approach is more space-efficient and does not require knowing the heap API. Pick whichever feels more natural.

If an interviewer asks for a follow-up, the divide-and-conquer approach is a good card to play after presenting the heap solution.

Edge cases

• Empty input. lists = []. Return None. Both approaches handle this.
• All empty lists. lists = [None, None]. No nodes get pushed to the heap. Return None.
• Single list. lists = [[1,2,3]]. The heap pops nodes one by one and rebuilds the same list. Divide and conquer returns it directly.
• Lists of different lengths. lists = [[1], [2,3,4,5]]. Works fine. The heap naturally handles lists running out at different times.
• Duplicate values. lists = [[1,1], [1,1]]. The tie-breaking index in the heap tuple handles this cleanly.

The building blocks

Merge K Sorted Lists is built from two building blocks that show up across many LeetCode problems.

Min heap for global minimum tracking

Push one representative element from each source into the heap. Pop the minimum, process it, and push its replacement. This pattern appears whenever you need to efficiently track the smallest (or largest) element across multiple streams or groups.

The template:

import heapq

heap = []
for i, source in enumerate(sources):
    if source:
        heapq.heappush(heap, (source[0], i, source))

while heap:
    val, i, source = heapq.heappop(heap)
    process(val)
    next_val = advance(source)
    if next_val is not None:
        heapq.heappush(heap, (next_val, i, source))

This same building block powers Kth Largest Element (heap of size k), Meeting Rooms II (heap of end times), and problems like "merge k sorted arrays" or "find the smallest range covering k lists."

Merge two sorted sequences

The merge function is the core of merge sort. Compare heads, pick the smaller one, advance that pointer. Repeat. When one sequence runs out, append the rest of the other.

def merge_two(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and 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 if l1 else l2
    return dummy.next

This is the same merge used in Merge Sorted Array (adapted for arrays rather than linked lists). The two-pointer merge is also the foundation for the divide-and-conquer approach: if you can merge two lists, you can merge k lists by pairing them up recursively.

Complexity summary

Why you will forget this (and how to fix it)

The high-level idea is easy to remember: "use a heap to always grab the smallest head." But the details trip people up. How do you break ties in the heap? What do you push after popping? How do you handle lists that run out?

For the divide-and-conquer approach, the details are different but equally tricky: how do you handle an odd number of lists? What does the merge-two function look like for linked lists specifically?

These are exactly the kind of implementation details that fade between practice sessions. Spaced repetition fixes this. You type the solution from scratch, check it, then do it again a few days later. After a few reps, the tie-breaking tuple trick and the dummy-head pattern become automatic.

CodeBricks drills both approaches separately. The heap version and the divide-and-conquer version are independent building blocks, each on its own SRS schedule. You reinforce them at exactly the right intervals.

Related posts

• Merge Sorted Array - The two-pointer merge building block, applied to arrays instead of linked lists
• Meeting Rooms II - Another min heap problem where the heap tracks "the earliest ending resource"

---

Visual Learner? See how heaps maintain order with our Heap Data Structure Guide -- the same structure powering the min heap merge.