【leetcode100-034】【链表/优先队列】合并k个升序链表

本文主要是介绍【leetcode100-034】【链表/优先队列】合并k个升序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题干】

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

【思路】

• 其实就是多路归并
• 用一个优先队列简化k个头部的比较和选最小节点的过程
• 然后就只剩一些细节处理啦
• 都没啥好写的今天这题。。。

【题解】

class Solution {
public:struct Status {int val;ListNode *ptr;bool operator < (const Status &rhs) const {return val > rhs.val;}};priority_queue <Status> q;ListNode* mergeKLists(vector<ListNode*>& lists) {for (auto node: lists) {if (node) q.push({node->val, node});}ListNode head, *tail = &head;while (!q.empty()) {auto f = q.top(); q.pop();tail->next = f.ptr; tail = tail->next;if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});}return head.next;}
};

这篇关于【leetcode100-034】【链表/优先队列】合并k个升序链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---