Problem #23: Merge k Sorted Lists

Intuition & Strategy Breakdown

Use a min-heap (priority queue) containing the head nodes of all K lists. Extract the smallest node, append it to the result list, and push its next node into the heap until empty.

Python Solution

import heapq


class Solution:
    def mergeKLists(self, lists):
        dummy = ListNode(0)
        tail = dummy
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        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

Java Solution

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue pq = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            tail.next = cur;
            tail = cur;
            if (cur.next != null) pq.offer(cur.next);
        }
        return dummy.next;
    }
}