LeetCode. 23. Merge k Sorted Lists

Problem

Approach

Keep the current head of every non-empty input list in a min-heap. At each step, the heap contains exactly the smallest unmerged node from each list that still has nodes. Therefore, its minimum is the smallest node remaining across all lists and can be appended to the result. After removing that node, enqueue its successor before linking the removed node; saving the successor first keeps the unmerged input chain available while the node is reused.

The result uses the original input nodes rather than allocating replacement nodes. A dummy head simplifies appending. When the heap becomes empty, explicitly set the final tail’s next to null so the result is terminated and cannot retain an old link that would create a cycle. An empty array or an array containing only null heads naturally returns null.

For N total nodes and K input lists, each node is inserted into and removed from a heap at most once, with heap operations costing O(log K). The time complexity is O(N log K) and the auxiliary heap space is O(K).

Java

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap =
                new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummy = new ListNode();
        ListNode tail = dummy;

        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            ListNode successor = node.next;
            if (successor != null) {
                minHeap.offer(successor);
            }
            tail.next = node;
            tail = node;
        }

        tail.next = null;
        return dummy.next;
    }
}