Merge k Sorted Lists | Leetcode 23

Welcome to our deep dive on Merge k Sorted Lists (Leetcode 23). This problem perfectly demonstrates the scalable power of Heaps and Divide-and-Conquer when moving beyond two trivial arrays!

Problem Statement

You are given an array of k linked-lists lists, each linked-list is 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]] => Output: [1,1,2,3,4,4,5,6]

Approach 1: Min-Heap (Priority Queue) O(N log K)

Because each list is independently already sorted, the absolute smallest element across all lists right now must be one of the k current head nodes!

Therefore, we can insert all k nodes into a Minimum Priority Queue. We pop the smallest node, attach it to our results LinkedList, and then immediately push that node's .next into the queue!

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Python heapq compares full objects if the first item (val) ties, 
        # so we inject an explicit counter to avoid comparing ListNode memory.
        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

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (23)