题解 | #牛群的合并#

考察的知识点：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;
    }
};