LeetCode23 合并K个升序链表

发表于 | 分类于 |
字数统计: 320 | 阅读时长 ≈ 1

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

题面

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法

考虑归并，只是这里推广到k个链表，对于找出当前最小的表头，可以使用优先队列
存储所有的表头，复习一下priority_queue自定义排序规则的写法
包括后续实现的细节 如何进行归并的过程

代码

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
/**
 * 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 cmp { //自定义排序规则结构体
        bool operator()(const ListNode* pa, const ListNode* pb) {
            int a = pa -> val, b = pb -> val;
            return a > b;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for(auto head: lists) {
            if (head != nullptr){
                pq.push(head);
            }
        }
        if (pq.empty()) return nullptr;
        ListNode* ret = new ListNode(), *now = ret;
        while(pq.size()) {
            now -> next = pq.top(); // 由于最后一个结点的next一定是nullptr
            now = now -> next;
            pq.pop();
            if (now -> next) { // 如果当前链表还有后续元素
                pq.push(now -> next);
            }
        }
        return ret -> next;

    }
};