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. Priority Queue (Min-Heap): Use a min-heap data structure to efficiently manage the heads of all k lists. The min-heap will store (value, ListNode) pairs, allowing us to easily access the smallest node across all lists.

3. Initialization: Add the head of each non-null list to the min-heap.

4. Iterative Merging: While the min-heap is not empty:

   • Extract the minimum element (smallest node) from the heap.
   • Add the node's value to the result list.
   • If the extracted node has a next node, add the next node to the heap.

5. Return Result: Return the merged sorted linked list.

Explanation

The key to solving this problem efficiently is using a min-heap. A min-heap ensures that we always have access to the smallest node among all the input lists. By repeatedly extracting the minimum and adding the next node from the corresponding list, we effectively merge the sorted lists in linear time relative to the total number of nodes. A naive approach that compares all nodes repeatedly would be significantly slower (O(N^2) where N is the total number of nodes).

Code

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if (lists == null || lists.Length == 0) {
            return null;
        }

        PriorityQueue<(int, ListNode), (int, ListNode)> minHeap = new PriorityQueue<(int, ListNode), (int, ListNode)>();

        // Add the head of each list to the min-heap
        for (int i = 0; i < lists.Length; i++) {
            if (lists[i] != null) {
                minHeap.Enqueue((lists[i].val, lists[i]), (lists[i].val, lists[i]));
            }
        }

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

        // Iteratively merge the lists
        while (minHeap.Count > 0) {
            (int val, ListNode node) = minHeap.Dequeue();
            current.next = node;
            current = current.next;

            if (node.next != null) {
                minHeap.Enqueue((node.next.val, node.next), (node.next.val, node.next));
            }
        }

        return dummy.next;
    }
}

Complexity

• Time Complexity: O(N log k), where N is the total number of nodes in all lists and k is the number of lists. Adding each node to the heap takes O(log k) time, and we do this N times.

• Space Complexity: O(k), as the heap can contain at most k nodes (one from each list). The space used by the resulting linked list is O(N), but this is considered separate from the algorithm's space complexity.