How Do You Merge K Sorted Linked Lists?

Learn how to merge k sorted linked lists in O(N log k) time using a min-heap, with a full Python example.

hardQ96 of 227 in Data Structures & Algorithms Est. time: 6 minsLast updated: July 2026

Expected Interview Answer

K sorted linked lists are merged efficiently in O(N log k) time by using a min-heap of size k that always holds the current head of each list, repeatedly popping the smallest node and pushing its successor, where N is the total number of nodes across all lists.

Seed the heap with the head node of each of the k lists, keyed by node value. On each step, pop the smallest node from the heap, append it to the result list, and if that node has a next node, push the successor into the heap. This repeats until the heap is empty, doing N total pops and pushes, each costing O(log k), giving O(N log k) overall with only O(k) extra space for the heap. A divide-and-conquer alternative pairs up lists and merges them two at a time in a binary reduction, also achieving O(N log k) since there are log k merge rounds and each round processes all N nodes. Naively merging lists one at a time into a running result gives O(N * k), which is worse whenever k is more than a small constant.

O(N log k) time using a min-heap of size k
O(k) extra space, independent of total node count
Divide-and-conquer variant matches the same complexity
Both avoid the O(N * k) cost of sequential pairwise merging

AI Mentor Explanation

Merging k sorted lists is like combining k separately sorted stacks of scorecards from k different grounds into one master sorted stack. Instead of comparing all k stacks' top cards by eye each time, you keep the k top cards in a small priority tray that always surfaces the lowest score; you take that card, place it on the master stack, then refill the tray from whichever ground's stack it came from. Because the tray only ever holds k cards, each pick-and-refill costs proportional to log k, and you repeat this for every card across all grounds. This beats merging the stacks two grounds at a time in sequence, which would redo comparisons far more often as the master stack grows.

Step-by-Step Explanation

Step 1
Seed a min-heap with k heads
Push the head node of every list into a min-heap keyed by node value, size at most k.
Step 2
Pop the smallest node
Remove the minimum from the heap and append it to the merged result list.
Step 3
Push its successor
If the popped node has a next node, push that successor into the heap.
Step 4
Repeat until the heap is empty
N total pops/pushes at O(log k) each give O(N log k) time overall.

What Interviewer Expects

Propose the min-heap-of-size-k approach with correct complexity O(N log k)
Know the divide-and-conquer pairwise-merge alternative and why it matches the same complexity
Reject naive sequential merging as O(N * k)
Correctly handle empty input lists and lists of different lengths

Common Mistakes

Merging lists two at a time sequentially, giving O(N * k) instead of O(N log k)
Forgetting to push the popped node's successor back into the heap
Not handling empty lists among the k inputs
Miscounting the heap size as k when it should track only currently active list heads

Best Answer (HR Friendly)

“I keep a small heap that always holds the current smallest head node across all k lists. I keep popping the smallest, appending it to the result, and pushing in whatever came next from that same list, which merges everything in O(N log k) time using only O(k) extra memory.”

Code Example

Merge k sorted linked lists with a min-heap

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 = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Follow-up Questions

How would the divide-and-conquer pairwise merge approach work instead of a heap?
Why does naive sequential merging cost O(N * k)?
How would you adapt this to merge k sorted arrays instead of linked lists?
How would you handle ties in value across different lists in the heap comparator?

MCQ Practice

1. What is the time complexity of merging k sorted linked lists with a min-heap of size k?

2. What is pushed into the heap immediately after popping a node during the merge?

3. What is the extra space complexity of the min-heap approach, excluding the output list?

Flash Cards

1 / 4

How Do You Merge K Sorted Linked Lists?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Seed a min-heap with k heads

Pop the smallest node

Push its successor

Repeat until the heap is empty