本文主要是介绍【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个升序链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!