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;
}