LeetCode Problem

Problem Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Examples

Input: [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length won't exceed 10^4.

Follow-up

Approach to Solve

Use a min-heap to merge the k lists.

Code Implementation

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        dummy = ListNode(0)
        current = dummy
        while heap:
            val, i, node = heapq.heappop(heap)
            current.next = ListNode(val)
            current = current.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.add(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            current.next = node;
            current = current.next;
            if (node.next != null) {
                minHeap.add(node.next);
            }
        }
        return dummy.next;
    }

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (ListNode* node : lists) {
            while (node) {
                minHeap.push(node->val);
                node = node->next;
            }
        }
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        while (!minHeap.empty()) {
            current->next = new ListNode(minHeap.top());
            minHeap.pop();
            current = current->next;
        }
        return dummy->next;
    }
};

Explanation

This solution uses a min-heap to efficiently merge k sorted linked lists. Here's a detailed explanation of the algorithm:

Initialize a min-heap: We start by creating a min-heap that will store the nodes from all the lists. The heap is ordered by the node values.
Populate the heap: We iterate through all the input lists and add the first node of each non-empty list to the heap. Each heap entry contains the node's value, list index, and the node itself.
Create a dummy node: We create a dummy node to simplify the merging process, especially when handling the head of the merged list.
Merge process:
- While the heap is not empty, we do the following: a. Pop the top node from the heap (the node with the smallest value). b. Add this node to our result list. c. If this node has a next node, we push that next node onto the heap.
Return the merged list: We return the next node of the dummy node, which is the head of our merged list.

This approach is efficient because:

We only need to compare k elements at a time (the first elements of each list), which is handled efficiently by the heap.
Each element is pushed and popped from the heap at most once.
The heap operations (push and pop) take O(log k) time, where k is the number of lists.

Time Complexity: O(N log k), where N is the total number of nodes across all lists, and k is the number of lists. Each of the N nodes is pushed and popped from the heap once, and each such operation takes O(log k) time.

Space Complexity: O(k), as the heap will contain at most k nodes at any time (one from each list).

This solution is particularly effective when dealing with a large number of sorted lists, as it efficiently manages the comparison and merging process using the heap data structure.

Complexity

Time Complexity: O(N log k)
Space Complexity: O(k)

LeetSolved

Merge k Sorted Lists