Merge K sorted lists using a min-heap.

Problem. Given an array of k sorted linked lists, merge them into one sorted list and return its head. Let N be the total number of nodes.

Brute force — collect and sort, O(N log N)

Dump every value into an array, sort it, rebuild a list. Correct, but it throws away the fact that each input is already sorted and ignores the linked structure.

Optimal (min-heap) — O(N log k) time, O(k) space

At any moment the global minimum among all lists is one of the k list heads. A min-heap of the current heads surfaces it in O(log k): poll the smallest head, append it to the result, then push that node's successor. The heap never exceeds k entries.

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap =
        new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists)
        if (head != null) heap.offer(head);   // seed with each non-null head

    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode min = heap.poll();            // smallest head across all lists
        tail.next = min;
        tail = min;
        if (min.next != null) heap.offer(min.next);  // pull the next from that list
    }
    return dummy.next;
}

Each of the N nodes is offered and polled exactly once at O(log k), giving O(N log k). The dummy head removes the special case for the first node.

Alternative — divide & conquer, same O(N log k)

Pairwise-merge the lists in a tournament: merge k/2 pairs, then k/4, and so on through log k rounds, each touching all N nodes. Same asymptotic cost, O(1) extra space beyond recursion, and no comparator — useful to mention as the heap-free option.