solved 'Merge k Sorted Lists' on LeetCode https://leetcode.com/problems/merge-k-sorted-lists/

merge_k_ls.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
// Divide and conquer.
// From https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue?show=10537#a10537
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        lists_ptr_ = &lists;
        return mergeKLists(0, lists.size());
    }

private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode pseudo_head(-1);
        ListNode *to_append = &pseudo_head;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                to_append->next = l1;
                l1 = l1->next;
            } else {
                to_append->next = l2;
                l2 = l2->next;
            }
            to_append = to_append->next;
        }
        to_append->next = l1 ? l1 : l2;
        return pseudo_head.next;
    }
    
    ListNode* mergeKLists(int start, int end) {
        int sz = end - start;
        switch (sz) {
            case 0:
                return NULL;
            case 1:
                return lists_ptr_->at(start);
            case 2:
                return mergeTwoLists(lists_ptr_->at(start), lists_ptr_->at(start + 1));
            default:
                return mergeTwoLists(
                    mergeKLists(start, start + sz / 2), mergeKLists(start + sz / 2, end));
        }
    }
    
    vector<ListNode*> *lists_ptr_;
};

merge_k_ls.py

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Use heap.
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = [(ls.val, ls) for ls in lists if ls]
        heapq.heapify(heap)
        to_append = pseudo_head = ListNode(-1)
        
        replacetop, pop = heapq.heapreplace, heapq.heappop
        while heap:
            val, ls = heap[0]
            if ls.next:
                replacetop(heap, (ls.next.val, ls.next))
            else:
                pop(heap)

            to_append.next = ls
            to_append = to_append.next

        return pseudo_head.next