Merge k Sorted Lists hard

Problem Statement

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example 1

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2

Input: lists = [] Output: []

Steps

1. Handle Empty Input: If the input list lists is empty or contains only null lists, return an empty list.

2. PriorityQueue for Comparison: Utilize a PriorityQueue (min-heap) to efficiently manage the heads of all k sorted lists. The PriorityQueue will automatically order the nodes based on their values. We'll use a custom comparator to compare ListNode objects based on their val property.

3. Iterative Merging:

   • Initialize a dummy head node to simplify the construction of the merged list.
   • Add the head nodes of all non-null input lists to the PriorityQueue.
   • While the PriorityQueue is not empty:
     • Remove the node with the smallest value (the head of the smallest sublist).
     • Add this node to the merged list.
     • If the removed node has a next node, add that next node to the PriorityQueue.

4. Return Merged List: Return the next node after the dummy head, which is the head of the merged sorted list.

Explanation

The key to efficiently solving this problem is using a priority queue (min-heap). A min-heap keeps track of the smallest element at the top. By placing the heads of all k sorted lists into the min-heap, we can repeatedly extract the smallest element, add it to our result, and replace it with the next element from its original list. This ensures that the merged list is always built in sorted order. The time complexity is dominated by the number of nodes processed, while the space complexity comes from the priority queue.

Code

import java.util.PriorityQueue;

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) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> a.val - b.val); // Min-heap comparator

        // Add the head nodes of all lists to the priority queue
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }

        ListNode dummy = new ListNode(0); // Dummy node to simplify construction
        ListNode tail = dummy;

        while (!pq.isEmpty()) {
            ListNode curr = pq.poll(); // Get the smallest node
            tail.next = curr; // Add it to the merged list
            tail = tail.next; // Move the tail pointer

            if (curr.next != null) {
                pq.offer(curr.next); // Add the next node from the same list
            }
        }

        return dummy.next; // Return the head of the merged list
    }
}

Complexity

• Time Complexity: O(N log k), where N is the total number of nodes in all k lists and k is the number of linked lists. Each node is added to and removed from the priority queue once, which takes O(log k) time.

• Space Complexity: O(k), where k is the number of linked lists. The space complexity is dominated by the priority queue, which holds at most k nodes at any time (one for each list).