题解 | #牛群的合并#
牛群的合并
https://www.nowcoder.com/practice/d0cb24e1494e4f45a4b7d1a17db0daef
考察的知识点:k个有序链表的合并;
解答方法分析:
- 建立一个最小堆(优先队列)
minHeap
,用于存储所有链表的节点值,以实现按升序合并的效果。 - 遍历每个链表,将链表中的节点值逐个加入到最小堆中。
- 创建一个虚拟节点
dummy
作为合并后链表的头部,并定义一个指针curr
指向当前节点。 - 从最小堆中取出最小的节点值创建一个新节点,将节点值设为取出的值,并将该节点插入到合并后链表的末尾。然后更新
curr
指针指向插入的节点。 - 重复步骤 4,直到最小堆为空,所有节点均已插入合并后的链表。
- 返回虚拟头节点的
next
指针,即合并后的有序链表。
所用编程语言:C++;
完整编程代码:↓
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<int, vector<int>, greater<int>> minHeap; for (ListNode* cowList : lists) { while (cowList != nullptr) { minHeap.push(cowList->val); cowList = cowList->next; } } ListNode* dummy = new ListNode(-1); ListNode* curr = dummy; while (!minHeap.empty()) { curr->next = new ListNode(minHeap.top()); curr = curr->next; minHeap.pop(); } return dummy->next; } };