30ms C++ solution


  • 0
    Y
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.empty()) return nullptr;
            std::size_t low(0),high(lists.size()-1);
            while(low<high){
                std::size_t mid = low + (high - low)/2;
                while(low<high){
                    lists[low] = mergeTwoLists(lists[low],lists[high]);
                    ++ low;
                    -- high;
                }
                low = 0;
                high = mid;
            }
            return lists[0];
        }
    private:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode dummy(0),*pre(&dummy);
            while(l1 && l2){
                if(l1->val<=l2->val) { pre->next = l1; l1 = l1->next;}
                else {pre->next = l2; l2 = l2->next;}
                pre = pre->next;
            }
            if(l1) pre->next = l1;
            if(l2) pre->next = l2;
            return dummy.next;
        }  
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.