leetcode-23-链表题-合并K个排序链表

发表于 | 分类于

题目

1.png

解法

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// 同时比较所有链表的首节点，利用优先级队列，每次弹出最小值
class Solution {
public:
    // 定义比较操作
    struct cmp{
        bool operator()(ListNode *a, ListNode *b){
            return a->val > b->val;
        } 
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;
		
        // 使用优先级队列，每次弹出最小值
        priority_queue<ListNode* ,vector<ListNode*> , cmp> heapk;
        for(auto list : lists){
            if(list) heapk.push(list);
        }
        
        ListNode *res = new ListNode(-1);
        ListNode *tempRes = res;
        while(!heapk.empty()){
            ListNode *top = heapk.top();
            heapk.pop();
            tempRes->next = top;
            tempRes = tempRes->next;
            if(top->next) heapk.push(top->next);
        }

        tempRes = res->next;
        delete res;
        return tempRes;
    }
};