Merge k Sorted Lists Problem Solution

Merge k Sorted Lists Problem: 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 :

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

Merge k Sorted Lists Problem Solution

Problem Solution In Python

from heapq import *
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)
        minHeap = []
        for root in lists:
            if root:heappush(minHeap, root)
        head, tail = None, None
        while minHeap:
            node = heappop(minHeap)
            if not head:
                head = tail = node
            else:
                tail.next = node
                tail = tail.next
            if node.next:
                heappush(minHeap, node.next)
        return head

Problem solution in Java.

public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){
            public int compare(ListNode n1, ListNode n2){
                return n1.val-n2.val;
            }
        });
        ListNode head = null, prev = null;
        for(int i=0; i < lists.length; i++){
            if(lists[i] != null){
                pq.add(lists[i]);
                lists[i] = lists[i].next;
            }
        }
        while(!pq.isEmpty()){
            ListNode curr = pq.remove();
            if(head == null) 
                head = curr;
            else
                prev.next = curr;
            prev = curr;
            if(curr.next != null)
            pq.add(curr.next);
        }
        return head;
    }

Problem Solution In C++

class Solution {
public:
    ListNode* merge(ListNode* a, ListNode* b){
        ListNode* result = NULL;
        if (a == NULL)
            return b;
        else if (b == NULL)
            return a;
        if (a->val <= b->val){
            result = a;
            result->next = merge(a->next, b);
        } else {
            result = b;
            result->next = merge(a, b->next);
        }
        return result;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {  //merge pairs of lists in an iteration
        if (lists.size() == 0)
            return NULL;
        
        for(int i = lists.size() ; i > 1 ; i = ceil((float) i/2)){
            int j = 0;
            while(j < i/2){
                lists[j] = merge(lists[j], lists[i-j-1]);
                j++;
            }
        }
        return lists[0];
    }

Problem Solution In C

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    while (listsSize > 1) {
        bool odd = listsSize % 2;
        listsSize -= odd;

        for (int i = 0; i < listsSize; i+=2) {
            struct ListNode* l1 = *(lists+i);
            struct ListNode* l2 = *(lists+i+1);

            if (l1 == 0) { *(lists + (i >> 1)) = l2; continue; }
            if (l2 == 0) { *(lists + (i >> 1)) = l1; continue; }
            struct ListNode* head;
            struct ListNode* tail;
            if (l1->val < l2->val) {
                head = tail = l1;
                l1 = l1->next;
            } else {
                head = tail = l2;
                l2 = l2->next;
            }
            while (true) {
                if (l1 == 0) { tail->next = l2; break; }
                if (l2 == 0) { tail->next = l1; break; }
                if (l1->val < l2->val) {
                    tail->next = l1;
                    l1 = l1->next;
                } else {
                    tail->next = l2;
                    l2 = l2->next;
                }
                tail = tail->next;
            }
            *(lists + (i >> 1)) = head;
        }
        if (odd) *(lists + (listsSize >> 1)) = *(lists + listsSize);
        listsSize = (listsSize >> 1) + odd;
    }
    return *lists;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment