题解 | #牛群的合并#

牛群的合并

https://www.nowcoder.com/practice/d0cb24e1494e4f45a4b7d1a17db0daef

考察的知识点:k个有序链表的合并;

解答方法分析:

  1. 建立一个最小堆(优先队列) minHeap,用于存储所有链表的节点值,以实现按升序合并的效果。
  2. 遍历每个链表,将链表中的节点值逐个加入到最小堆中。
  3. 创建一个虚拟节点 dummy 作为合并后链表的头部,并定义一个指针 curr 指向当前节点。
  4. 从最小堆中取出最小的节点值创建一个新节点,将节点值设为取出的值,并将该节点插入到合并后链表的末尾。然后更新 curr 指针指向插入的节点。
  5. 重复步骤 4,直到最小堆为空,所有节点均已插入合并后的链表。
  6. 返回虚拟头节点的 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;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 12:23
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务