Merge K Sorted Lists

Table of Contents +

Merge K Sorted Lists is a step up from merging just two lists. It tests whether you can pick the right tool when the input grows. A naive merge still works. But a heap or a divide-and-conquer plan makes it much faster. That choice is what the interviewer is watching for.

🎯 The Problem

You must join many sorted lists into one sorted list. Here are the rules.

You get several linked lists.
Each list is already sorted in increasing order.
A linked list is a chain of nodes, each holding a value and a pointer to the next node.
Join them all into one sorted linked list.
Return the head of that joined list.

Input:
  list 1: 1 -> 4 -> 5
  list 2: 1 -> 3 -> 4
  list 3: 2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

We pick the smallest head across all lists, add it to the answer, and move forward in that list. Then repeat until every list is empty.

Here are the three input lists, each already sorted on its own.

🐢 Approach 1: Collect and Sort (Brute Force)

The idea in one line: dump every value into one array, sort it, then rebuild a list.

The idea:

Walk every list and copy all values into one big array.
Sort that array.
Build a fresh linked list from the sorted values.

Why it is weak:

It throws away the fact that each list is already sorted.
Sorting all n values costs O(n log n), where n is the total number of nodes.
We can do better by using the sorted order we were handed.

Here is the collect-and-sort code:

def merge_k_lists(lists):
    values = []
    for node in lists:
        while node:
            values.append(node.val)
            node = node.next
    values.sort()

    dummy = ListNode(0)
    cur = dummy
    for value in values:
        cur.next = ListNode(value)
        cur = cur.next
    return dummy.next

⚡ Approach 2: Min-Heap of Heads (Better)

The idea in one line: keep one head from each list in a min-heap and keep pulling the smallest.

The idea:

We only ever need the smallest current head across all lists.
A min-heap always hands you its smallest item fast, in O(log k) time, where k is the number of items.
Put the head of every list into the heap.

How it works:

Pop the smallest node and attach it to the answer.
If that node has a next node, push the next node into the heap.
Repeat until the heap is empty.
The heap holds at most k nodes, one per list.

Why it is fast:

Each of the n nodes is pushed and popped once.
Each push or pop costs O(log k).
So the total time is O(n log k). That beats brute force when k is small.

Here is the min-heap code:

import heapq


def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    cur = dummy
    while heap:
        value, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

⚡ Approach 3: Divide and Conquer (Best)

The idea in one line: merge the lists two at a time, like a knockout tournament, until one remains.

The idea:

Merging two sorted lists is easy and you may already know it.
Pair up the lists and merge them two at a time.
Then pair up the results and merge again.
Keep halving the count until one list remains.

How it works:

After each round the number of lists is cut in half.
There are about log k rounds.
In each round every node is touched once, so each round is O(n).

Why it is fast:

The total is again O(n log k), with no heap needed.
It needs only O(log k) stack space if recursive, or O(1) as a loop.
So it matches the heap on time and uses even less memory.

This is the divide-and-conquer merge as a tournament. Four lists become two, then two become one.

Steps to Solve

Make a min-heap that orders nodes by their value.
Push the head node of every non-empty list into the heap.
Pop the smallest node from the heap and attach it to the tail of the answer list.
If that node has a next node, push the next node into the heap.
Repeat until the heap is empty.
Return the answer list, skipping the dummy head node.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses heapq, the built-in min-heap. We push a tuple of value and an index so the heap can break ties without comparing nodes.

import heapq


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


def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):     # seed the heap with every head
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)                  # dummy head simplifies the build
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)   # smallest current head
        tail.next = node
        tail = tail.next
        if node.next:                    # push the next node from that list
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next


def build(values):
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head


lists = [build([1, 4, 5]), build([1, 3, 4]), build([2, 6])]
merged = merge_k_lists(lists)

out = []
while merged:
    out.append(str(merged.val))
    merged = merged.next
print(" -> ".join(out))

The output of the above code will be:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Let us read the Python min-heap version line by line, since the heap is the heart of the idea.

We import heapq, Python’s built-in min-heap. It always pops the smallest item first.

In merge_k_lists, we loop over every list and push its head onto the heap. We push a tuple (node.val, i, node). The first item is the value, so the heap orders by value. The second item i is the list index. We add it as a tie-breaker. A tie-breaker is a backup value used when two main values are equal. Without it, Python would try to compare the node objects when two values match, and that would crash because nodes are not comparable.

We make a dummy head node. Building a list is easier when you have a fake starting node, because the first real node attaches the same way as the rest.

Then the main loop runs while the heap has items. We pop the smallest tuple. We attach its node to the tail of our answer and move the tail forward. If that node has a next, we push the next node from the same list. So the heap always holds at most one node per list.

When the heap empties, every node is placed in sorted order. We return dummy.next, which skips the fake head.

⏱️ Time and Space Complexity

The brute force collects all n nodes and sorts them, which is O(n log n) time. The min-heap and the divide-and-conquer approaches both run in O(n log k), where k is the number of lists. When k is much smaller than n, log k is much smaller than log n, so they win. The heap needs O(k) extra space for the k heads. Divide and conquer needs O(log k) stack space if written recursively, or O(1) if written as a loop.

Approach	Time Complexity	Space Complexity
Collect all and sort	O(n log n)	O(n)
Min-heap of heads	O(n log k)	O(k)
Divide and conquer	O(n log k)	O(log k)

Tip

When you push linked-list nodes into a heap, always add a tie-breaker value like the list index. Otherwise the heap will try to compare two nodes when their values are equal, and that throws an error in most languages.

🧩 Key Takeaways

✅ Each list is already sorted, so do not throw that away by dumping into an array and sorting.
✅ A min-heap keeps only the current heads and always hands you the smallest one fast.
✅ Divide and conquer merges two lists at a time, halving the count each round.
✅ Both smart approaches run in O(n log k), which beats the O(n log n) brute force when k is small.
✅ Always add a tie-breaker when pushing nodes into a heap, or equal values cause a crash.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Reverse Nodes in k-Group
Merge Two Sorted Lists

Previous LRU Cache Next Reverse Nodes in k-Group

Merge K Sorted Lists

Follow Us

Follow Us