LeetCode23. 合并K个升序链表【优先队列】

﹏ヽ暗。殇╰゛Y 2022-09-09 06:03 230阅读 0赞

难度：困难  
题目描述：

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

示例 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 <= 104  
> 0 <= lists\[i\].length <= 500  
> \-104 <= lists\[i\]\[j\] <= 104  
> lists\[i\] 按 升序 排列  
> lists\[i\].length 的总和不超过 104

/** * 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 comp{ 
            bool operator()(ListNode *a,ListNode* b){ 
                return a->val>b->val;
            }
        };
        ListNode* mergeKLists(vector<ListNode*>& lists) { 
            int n=lists.size();
            if(n==0){ 
                return nullptr;
            }
            ListNode *ans=new ListNode(-1);
            ListNode *tmp = ans;
            priority_queue<ListNode*,vector<ListNode*>,comp> p;
            for(int i=0;i<n;i++){ 
                if(lists[i]!=nullptr)
                    p.push(lists[i]);
            }
            while(!p.empty()){ 
                ListNode* cur=p.top();
                p.pop();
                if(cur->next){ 
                    p.push(cur->next);
                }
                tmp->next = cur;
                tmp = tmp->next;
            }
            return ans->next;
        }
    };