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

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

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        if(lists.empty())return nullptr;
        priority_queue<ListNode*,vector<ListNode*>,campare>minheap;
        for(int i=0;i<lists.size();i++){
            if(lists[i]!=nullptr){
            minheap.push(lists[i]);}
        }
        ListNode* dummy=new ListNode(0);
        ListNode* cur=dummy;
        while (!minheap.empty()) {
            ListNode* node=minheap.top();
            minheap.pop();
            cur->next=node;
            cur=cur->next;
            if(node->next!=nullptr){
                node=node->next;
                minheap.push(node);
            }

        
        }
        return dummy->next;


    }
};

1. 使用优先队列（最小堆）：首先，你可以使用一个优先队列（最小堆）来存储所有链表的头节点，以便快速获取最小的节点。
2. 逐个处理节点：然后，从优先队列中取出最小的节点，将其添加到结果链表中，并更新该节点链表的头节点（如果它不是最后一个节点）。
3. 重复过程：重复上述过程，直到所有链表中的节点都被添加到结果链表中。
4. 返回结果链表的头节点。