LeetCode

LeetCode-23 合并K个升序链表

nkul · 9月6日 · 2020年 50次已读

和上题类似,但是比较时,需要比较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:
    struct com{
        bool operator() (ListNode* a,ListNode* b){
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector& lists) {
        priority_queue, com> p;
        auto  dummy = new ListNode(-1),tail =  dummy;
        for(auto i:lists){
            if(i) p.push(i);
        }
        while(p.size()){
            auto t = p.top();
            p.pop();
            tail  = tail->next = t;
            if(t->next) p.push(t->next);
        }
        return dummy->next;
    }
};

定义堆时,需要重载()符号,否则将会按地址进行比较,而不是链表值!

分治算法:每两个先合并,然后在k/2中继续每两个合并!

/**
 * 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& lists) {
        if(lists.size() == 0) return NULL;
        if(lists.size() == 1) return lists[0];
        if(lists.size() == 2) return merge2Lists(lists[0],lists[1]);

        int mid = lists.size()/2;
        //分治,分割成2分
        vector l1(mid);
        for(int i=0;i< mid;i++){
            l1[i] = lists[i];
        }
        vector l2(lists.size()-mid);
        for(int i=mid , j = 0;i< lists.size();i++,j++){
            l2[j] = lists[i];
        }
        return merge2Lists(mergeKLists(l1),mergeKLists(l2));
    }
    //合并两个链表
    ListNode* merge2Lists(ListNode* a,ListNode* b){
        auto dummy = new ListNode(-1),cur = dummy;
        while(a&&b){
            if(a->val < b->val){
                cur = cur->next = a;
                a = a->next;
            }
            else{
                cur = cur->next = b;
                b = b->next;
            }
        }
        if(a){
            cur->next = a;
        }
        if(b){
            cur->next = b;
        }
        return dummy->next;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!