题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <iterator>
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
	  //合并K个链表时，由于K的个数是随机的，所以直接进行合并不是很好操控，因为你不知到到底要操控几个链表，有点无从下手。看给的参数中，向量中存储的是K个链表的头节点指针，合并这K个链表，需要每次比较每一个链表的第一个节点，一次需要对K个链表的首节点进行比较，由于K来回变，手写一个比较函数不现实，可以考虑借助其他的数据结构——最小堆（优先队列）（存储空间动态变化，就不用在意K的值了）来代替比较函数，然后将比较结果插入到结果链表，将剩余的节点继续插入最小堆（priority_queue）进行自动排序，然后循环插入到结果队列，直到优先队列元素个数为空。
	  //定义比较方式，为后续构建优先队列做准备
        struct Compare {
            bool operator()(ListNode* a, ListNode* b) {
                return a->val > b->val;
            }
        };

        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        
        std::priority_queue<ListNode*, std::vector<ListNode*>, Compare> minHeap;
        for (ListNode* list : lists) {//将向量中的每一个链表的头节点指针存入到优先队列中。
            if (list) {
                minHeap.push(list);
            }
        }
        while (!minHeap.empty()) {//然后在依次取出，并将取出的链表节点的剩余节点存入优先队列。
            // 取出最小值的节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();

            // 将该节点加入结果链表
            current->next = minNode;
            current = current->next;
            if (minNode->next)
                minHeap.push(minNode->next);

        }

        ListNode* result = dummy->next;//准备返回结果指针

        // 释放虚拟头节点
        delete dummy;

        return result;


    }
};