Merge K Sorted Lists Heap DSA Solution

Learning Outcome

After this lesson, you should be able to use a heap to choose the next smallest node among k sorted streams.

Problem Statement

Given k sorted linked lists, merge them into one sorted linked list.

Input	Output	Why
`lists = [[1,4,5],[1,3,4],[2,6]]`	`[1,1,2,3,4,4,5,6]`	The smallest available list head is repeatedly appended to the output.

Brute Force Approach

Merge lists one by one. The growing merged list may be scanned repeatedly.

Optimized Approach

Push the first node of every non-empty list into a min-heap. Pop the smallest node, append it, and push its next node.

Exact Pseudocode

heap = first node of each non-empty list
dummy = new node
tail = dummy
while heap is not empty:
  node = pop smallest
  tail.next = node
  tail = tail.next
  if node.next exists:
    push node.next
return dummy.next

Reference Code

import heapq

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

        dummy = ListNode(0)
        tail = dummy
        while heap:
            _, 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

Sample Dry Run

Step	State	Result
Initialize	heap has heads 1,1,2	Smallest heads are ready
Pop 1	Append node and push its next 4	Output starts [1]
Pop 1 then 2	Push following nodes as needed	Output [1,1,2]
Finish	Heap becomes empty	All nodes are merged

Complexity

Measure	Value	Reason
Time	O(n log k)	Each of n nodes is pushed and popped from a heap of at most k nodes.
Space	O(k)	The heap stores at most one current node per list.

Edge Cases

Empty input lists should be skipped.
All lists empty should return null.
Duplicate values should remain in sorted order.

Interview Checklist

Push only non-null list heads.
Use a dummy node for easy output building.
After popping a node, push its next node if it exists.

FAQs

Why does the heap stay size k?

It stores at most one active node from each list at a time.

Why use a dummy node?

It avoids special handling for the first appended node.

What is the core pattern?

Min-heap multiway merge.

Merge K Sorted Lists: Min-Heap Multiway Merge Pattern