Neil Gajare

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy;
    auto tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
            
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    
    return dummy.next;
}

ListNode* merge_div_conq(std::vector<ListNode*>& lists) {
    // could be optimized by taking two lists at a time instead
    // of merging at end always
    while (lists.size() > 1) {
        auto merged = merge(lists[lists.size() - 1], lists[lists.size() - 2]);
        lists.pop_back();
        lists.pop_back();
        lists.emplace_back(merged);
    }
    return lists.empty() ? nullptr : lists.front();
}


class Solution {
public:
    #ifdef false
    // divide-and-conquer (slower than min-heap)
    ListNode* mergeKLists(vector<ListNode*>& lists) { 
        return merge_div_conq(lists);
    }
    #endif
    
    // solution with min-heap
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto compare =[](const ListNode* lhs, const ListNode* rhs) {
            return lhs->val > rhs->val;
        };
        
        using PriorityQueue = std::priority_queue<ListNode*,std::vector<ListNode*>,decltype(compare)>;
        PriorityQueue pq(compare);
        for (auto& l : lists) {
            if (l)
                pq.push(l);
        }
        
        ListNode dummy;
        auto tail = &dummy;
        while (!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            
            if (node->next) {
                pq.push(node->next);
            }
            
            tail->next = node;
            tail = tail->next;
        }
        
        return dummy.next;
    }
};