Problem 3 - Merge k sorted lists

Question

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 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: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length

• 0 <= k <= 104

• 0 <= lists[i].length <= 500

• -104 <= lists[i][j] <= 104

• lists[i] is sorted in ascending order.

• The sum of lists[i].length will not exceed 104.

Approach

This solution utilizes a min heap (PriorityQueue) to merge the k sorted lists. It starts by adding the head nodes of all the lists to the min heap. Then, it repeatedly extracts the minimum node from the heap and appends it to the result list. After appending a node, it adds the next node from the same list to the min heap if available. This process continues until the min heap is empty. Finally, it returns the merged sorted list.

Here’s a summary of the algorithm:

1. Create a min heap (PriorityQueue) and initialize it with the head nodes of all the lists.

2. Create a dummy node and a current pointer to keep track of the merged list.

3. While the min heap is not empty:

   • Extract the minimum node from the min heap.

   • Append the extracted node to the merged list.

   • If the extracted node has a next node, add it to the min heap.

4. Return the merged list.

The min heap helps ensure that the smallest node from each list is always at the top, allowing us to efficiently merge the lists in ascending order. By repeatedly extracting the minimum node and appending it to the merged list, we can merge all the lists into a single sorted list.

Solution

Solve it here

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // Add the head nodes of all lists to the min heap
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }

        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        // Perform merging by extracting the minimum node from the min heap
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            current.next = node;
            current = current.next;

            // Add the next node of the extracted node to the min heap
            if (node.next != null) {
                minHeap.offer(node.next);
            }
        }

        return dummy.next;
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(N log k), where N is the total number of nodes across all lists and k is the number of lists. The min heap operation to extract the minimum node takes O(log k) time, and we perform this operation N times in total (for each node). Thus, the overall time complexity is dominated by the min heap operations.

Space Complexity: The space complexity of this solution is O(k), as the min heap stores at most k nodes, where k is the number of lists. Additionally, we use a constant amount of extra space for creating the dummy node and maintaining the current pointer. Hence, the space complexity is considered O(k).