力扣-23题 合并K个升序链表（C++）- 链表_23. 合并 k 个升序链表c++

题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
题目如下：


解1、两两合并

/**
 * 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* res=nullptr;
        if(lists.size()==0) return res;
        if(lists.size()==1) return lists[0];
        for(int i=0;i<lists.size();i++){
            res=mergetwoKLists(res,lists[i]);
        }
        return res;
    }
    ListNode* mergetwoKLists(ListNode* l1,ListNode* l2){
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* dummy=new ListNode(-1),*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;
        }
        if(l1) tail->next=l1;
        else if(l2) tail->next=l2;

        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

解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<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists,int l,int r){
        if(l==r) return lists[l];
        if(l>r) return nullptr;
        int mid=l+(r-l)/2;//(l+r)>>1;可以，不能l+(r-l)>>1，右移还是不太懂她

        return mergetwoKLists(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    ListNode* mergetwoKLists(ListNode* l1,ListNode* l2){
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* dummy=new ListNode(-1),*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;
        }
        if(l1) tail->next=l1;
        else if(l2) tail->next=l2;

        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

解3、小顶堆

/**
 * 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;
        priority_queue<ListNode*,vector<ListNode*>,Cmp> minheap;

        for(auto e:lists){
            if(e) minheap.push(e);
        }

        auto dummy=new ListNode(-1);
        auto tail=dummy;
        while(!minheap.empty()){
            auto top=minheap.top();
            minheap.pop();
            tail->next=top;
            tail=tail->next;
            if(top->next) minheap.push(top->next);
        }
        return dummy->next;
    }
private:
    struct Cmp{
        bool operator()(ListNode* l1,ListNode* l2){
            return l1->val > l2->val; //目的：优先出列判定为!cmp，所以反向定义实现最小值优先
        }
    };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39