【算法】合并k个已排序的链表

✨题目链接：

NC51 合并k个已排序的链表

✨题目描述 

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数 0≤𝑛≤50000≤n≤5000，每个节点的val满足 ∣𝑣𝑎𝑙∣<=1000∣val∣<=1000

要求：时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)O(nlogn)

✨示例1

📍输入

[{1,2,3},{4,5,6,7}]

📍输出

{1,2,3,4,5,6,7}

✨示例2

📍输入

[{1,2},{1,4,5},{6}]

📍输出

{1,1,2,4,5,6}

✨解题思路

 优先级队列：

• 把vector中所有链表头节点丢进优先级队列中
• 提供一个比较链表val大小的仿函数
• 如果队列不为空，取队列顶元素插入新链表
• 弹出队头元素用tmp接收，让tmp=tmp->next
• 把tmp再重新插入队列
• 最后返回newnode

✨代码

struct cmp {//重载小顶堆比较方式bool operator()(ListNode* a, ListNode* b) {return  a->val > b->val;}
};
class Solution {public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> priorityq;for (int i = 0; i < lists.size(); i++){if(lists[i]!=nullptr){priorityq.push(lists[i]);}}ListNode* newnode = new ListNode(0);ListNode* cur = newnode;ListNode* tmp;while (!priorityq.empty()){cur->next = priorityq.top();tmp = priorityq.top();priorityq.pop();tmp = tmp->next;if (tmp != nullptr){priorityq.push(tmp);}cur = cur->next;}return newnode->next;}
};

---

※ 如果文章对你有帮助的话，可以点赞收藏！！谢谢支持