[数据结构与算法]力扣23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

一开始没啥太好的思路，就是前两个链表先合并，结果再跟第三个合并，结果再跟第四个合并...以此类推直到结束。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* tmp=nullptr;
        for(int i=0;i<lists.size();i++){
            tmp=merge(tmp,lists[i]);
        }
        return tmp;
    }
    ListNode* merge(ListNode* a,ListNode* b){
        ListNode* head=new ListNode(0);
        ListNode* tmp=head;
        while(a!=nullptr && b!=nullptr){
            if(a->val < b->val){
                tmp->next=a;
                a=a->next;
            }
            else{
                tmp->next=b;
                b=b->next;
            }
            tmp=tmp->next;
        }
        tmp->next= b ? b : a;
        return head->next;
    }
};

但是有点惨不忍睹啊。

又试了下暴力

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty()) return NULL;
        for (int i = 0; i < lists.size() - 1; ++i) 
            lists[i+1] = merge(lists[i], lists[i+1]);
        return lists[lists.size() - 1];
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l1) p->next = l1;
        if(l2) p->next = l2;
        return dummy->next;
    }
};

结果差不多0.0

然后从大神那里get到了用分治，果然起飞。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if( lists.size()==0 ){
            return nullptr;
        }
        
        int interval=1;
        while(interval<lists.size() ){
            for( int i=0 ;i+interval<lists.size() ; i+=(interval*2) ){
                lists[i] = mergeTwoLists(lists[i],lists[i+interval]);
            }
            interval<<=1;
        }
        return lists[0];
    } 

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if( l1==nullptr ){
            return l2;
        }
        if( l2==nullptr ){
            return l1;
        }
        
        ListNode* fakehead = new ListNode;
        ListNode* cur = fakehead;
        //l1 and l2 are not empty
        while( l1!=nullptr && l2!= nullptr ){
            if( l1->val <= l2->val ){
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        while( l1!=nullptr ){
            cur->next = l1;
            cur = cur->next;
            l1 = l1->next;
        }
        while(l2 != nullptr){
            cur->next = l2;
            cur = cur->next;
            l2 = l2->next;
        } 

        ListNode * ret =  fakehead->next;
        delete fakehead;

        return ret;
    }
};

就是内存消耗多了0.1MB，代码长了点hhh。

计算机201? ?LW