Merge k Sorted Lists

23. 合并K个升序链表

分析

使用优先队列
- 创建一个优先队列 heap，用于存储链表节点
- 队列中的元素按节点值从小到大排序（小根堆）
- 使用一个自定义比较器 cmp 来实现小根堆的逻辑
初始化优先队列
- 将所有链表的头节点（如果非空）加入优先队列
归并链表
- 每次从优先队列中取出值最小的节点 temp，将其加入新链表
- 如果 temp 节点还有下一个节点，则将其 next 节点加入优先队列
- 重复以上步骤，直到队列为空

时间复杂度

优先队列的插入和删除操作的时间复杂度为 O(logk)，其中 k 是链表的数量
每个节点都会被插入和删除一次，因此总时间复杂度为 O(nlogk)，其中 n 是链表中所有节点的总数

空间复杂度

优先队列最多同时存储 k 个节点，因此空间复杂度为 O(k)

C++代码

 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
43


class Solution
{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        // 自定义比较器，用于优先队列排序
        struct cmp
        {
            bool operator()(ListNode* a, ListNode* b)
            {
                return a->val > b->val; // 小根堆
            }
        };

        // 定义优先队列（小根堆）
        std::priority_queue<ListNode*, std::vector<ListNode*>, cmp> heap;

        // 初始化优先队列，将每个链表的头节点加入堆中
        for (ListNode* li : lists)
            if (li)
                heap.push(li);

        // 定义虚拟头节点，便于操作新链表
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        // 从优先队列中逐步取出最小值节点，并更新链表
        while (!heap.empty())
        {
            ListNode* temp = heap.top(); // 获取当前最小值节点
            heap.pop();                  // 将其从堆中移除
            cur = cur->next = temp;      // 将其加入新链表
            if (temp->next)              // 如果有后续节点，将后续节点加入堆中
            {
                temp = temp->next;
                heap.push(temp);
            }
        }

        // 返回合并后的链表
        return dummy->next;
    }
};