Merge k Sorted Lists Leetcode Solution

Problem Statement

The Merge k Sorted Lists LeetCode Solution – “Merge k Sorted Lists” states that given the array of k linked lists, where each linked list has its values sorted in ascending order. We need to merge all the k-linked lists into one single linked list and return the head of the linked list.

Example:

Input:  lists = [[1,4,5],[1,3,4],[2,6]]

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

Explanation:

• Consider all values in ascending order: [1, 1, 2, 3, 4, 4, 5, 6].
• We need to form a linked list with the above values.

Input:  lists = []

Output: []

Explanation:

• The input array is empty, return the null pointer as the head of the linked list.

Approach

Idea:

1. The main idea to solve this problem is to use Priority Queue.
2. Iterate in the array of linked lists and store all pairs {values, head pointers} in the min-heap.
3.  Each time, pop out the node with the minimum value from the min-heap and make it the next node of the newly formed linked list.
4. Also, check if the popped node has the next node, then insert the pair {value, next node} in the min-heap again.
5. Above mentioned process, results in the formation of a new linked list with all the values sorted in ascending order since every time, we’re extracting the node with minimum value and making it the next node of the new linked list.
6. Finally, we have merged k linked lists.

Code

Merge k Sorted Lists Leetcode C++ Solution:

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

Merge k Sorted Lists Leetcode Java Solution:

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

Complexity Analysis for Merge k Sorted Lists Leetcode Solution

Time Complexity

The time complexity of the above code is O(NKlogK). Each node is pushed into the min-heap once and there are total at most N*K nodes in the given array of linked lists, where N = maximum number of nodes in a single linked list and K = size of the array of the linked list.

Space Complexity

The space complexity of the above code is O(K) since we’re using a min-heap of maximum size k.

Reference:- https://en.wikipedia.org/wiki/Linked_list