LCR 078. 合并 K 个升序链表 - 力扣（LeetCode）LCR 078. 合并 K 个升序链表 - 给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6示例 2：输入：lists = []输出：[]示例 3：输入：lists = [[]]输出：[] 提示： * k == lists.length * 0 <= k <= 10^4 * 0 <= lists[i].length <= 500 * -10^4 <= lists[i][j] <= 10^4 * lists[i] 按 升序 排列 * lists[i].length 的总和不超过 10^4 注意：本题与主站 23 题相同： https://leetcode.cn/problems/merge-k-sorted-lists/ [https://leetcode.cn/problems/merge-k-sorted-lists/]https://leetcode.cn/problems/vvXgSW/

题目描述

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

示例： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]

核心难点：多条有序链表多路归并，如何高效持续拿到全局最小值节点。

思路分析

多条升序链表，每一条链表头部都是当前链表最小值。我们需要不断从所有链表头部选出全局最小节点接入结果链表。 暴力思路：每次遍历全部链表头寻找最小值，时间复杂度 \(O(kN)\)，效率低下。

优化方案：小根堆（优先队列）

1. 将所有非空链表的头节点放入小根堆；堆自动维护堆顶为全局最小值；
2. 循环取出堆顶最小节点，接入结果链表；
3. 如果取出的节点存在后继节点，将后继节点推入堆；
4. 堆为空时，全部节点处理完毕，返回合并链表。

/**
 * 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) {}
 * };
 */
 #include<queue>
class Solution {
public:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            // priority\_queue小根堆规则：返回true，l1放下面
            return l1->val > l2->val;
        }

    } ;
   
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n=lists.size();
        //创建小根堆
        priority_queue<ListNode*, vector<ListNode*>,cmp > minHeap;
        //让所有的头节点进入小根堆
        for(auto l :lists)
        if(l) minHeap.push(l);
        //合并k个有序链表
        ListNode*ret=new ListNode(0);
        ListNode*prev=ret;
        while(!minHeap.empty())
        {
            ListNode* t=minHeap.top();
            minHeap.pop();
            prev->next=t;
            prev=t;
            if(t->next)
            minHeap.push(t->next);
        }
        prev=ret->next;
        delete ret;
        return prev;

    }
};