Merge K Sorted Lists: Heap and Divide-and-Conquer Solutions in Python

Merge k Sorted Lists (LeetCode 23) asks you to merge k sorted linked lists into one sorted list. It's popular because the brute force is obvious, and the interesting part is choosing between two good ways to do better: a min-heap or divide and conquer. Both run in O(N log k), where N is the total number of nodes.

The problem

Given an array of k linked lists, each sorted in ascending order, merge them into one sorted linked list and return it.

Example: [[1,4,5],[1,3,4],[2,6]] becomes [1,1,2,3,4,4,5,6].

Questions to ask the interviewer:

• Can the array be empty, or contain empty lists? (Yes, handle both.)
• Should I reuse the existing nodes or create new ones? (Reusing is fine and saves memory.)
• Are duplicate values possible? (Yes, so keep the merge stable if it matters.)

Brute force

Collect all values into an array, sort it, and rebuild a list. Time is O(N log N) and space is O(N). It works, but it ignores that each list is already sorted, so it's rarely accepted as the final answer.

Approach 1: a min-heap

Keep one pointer per list. The next node in the output is always the smallest among the current heads, so keep the heads in a min-heap.

1. Push the head of each non-empty list onto the heap.
2. Pop the smallest, append it to the result, and push its next node if there is one.
3. Repeat until the heap is empty.

import heapq

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

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    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))
    return dummy.next

The index i is a tiebreaker. Without it, two entries with equal values would make Python compare ListNode objects, which raises a TypeError.

Complexity: each of the N nodes goes into the heap once and comes out once, and each operation costs O(log k), so time is O(N log k). The heap holds at most k nodes, so extra space is O(k).

Approach 2: divide and conquer

Merging two sorted lists is easy and takes O(n) time. Merge the lists in pairs, then merge the results in pairs, and so on, like a tournament.

def merge_two(a, b):
    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
    return dummy.next

def merge_k_lists_dc(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            other = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(lists[i], other))
        lists = merged
    return lists[0]

Complexity: there are about log k rounds, and each round touches all N nodes once, so time is O(N log k). The loop version needs only O(1) extra space apart from the list of heads.

Why not merge one by one?

Merging list 1 with list 2, then the result with list 3, and so on, looks natural but costs more. The first list gets copied through k merges. If every list has n nodes, the total work is about n x (1 + 2 + ... + k), which is O(n k squared). Pairing lists keeps the sizes balanced, so each node is touched about log k times.

Comparing the two

If an interviewer says the lists are too large for memory and arrive as streams, the heap approach extends naturally, since it only needs the current head of each stream.

Edge cases to test

How to explain it in an interview

1. State the brute force and why it's wasteful.
2. Say the key observation: the next output node is the smallest current head.
3. Pick the heap, write it, and mention the tiebreaker.
4. State the complexity: O(N log k) time and O(k) space.
5. Offer divide and conquer as the O(1) space alternative.
6. Test with an empty input and one with duplicates.

I tested both versions above against a sorting-based check on 3,000 random inputs, including empty lists, before publishing. Doing a quick random check like that is a good habit when you practice.

Related practice

If this was easy, try Merge Two Sorted Lists first, then Sort List and Find Median from Data Stream, which use the same ideas. See our Big O cheat sheet for the complexity terms, the longest common substring guide for dynamic programming, and the coding interview assistant guide for how to practice.

Talk through your approach aloud while you code. A mock interview transcript shows whether you explained the key observation before writing. Follow the employer's rules on AI tools in any live assessment.