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

使用小根堆即可完成任务，或者使用败者树也可以

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
 #include<vector>
 #include<queue>
 struct Status {
    int val;
    int index;
    Status(int a, int b): val(a), index(b) {}
    bool operator< (Status s) const {
        return s.val < val;
    }
 };
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 建立小根堆
        priority_queue<Status> my_queue;

        // 获取列表数目
        int k = lists.size();
        // 声明并初始化数组用于存储存储每个列表的访问指针
        vector<ListNode*> indexs;
        for (int i = 0; i < k; i++) {
            if (lists[i] == NULL) {
                indexs.push_back(NULL);
            } else {
                indexs.push_back(lists[i]);
                // 初始化堆
                Status temp(lists[i]->val, i);
                my_queue.push(temp);
            }
        }

        // 头指针与尾指针
        ListNode* rear = (ListNode*)malloc(sizeof(ListNode));
        rear->next = NULL;
        ListNode* head = rear;

        while(!my_queue.empty()) {
            int value = my_queue.top().val;
            int index = my_queue.top().index;
            my_queue.pop();

            ListNode* node = (ListNode*)malloc(sizeof(ListNode));
            node->val = value;
            node->next = NULL;
            rear->next = node;
            rear = rear->next;

            // 更新指针
            indexs[index] = indexs[index]->next;
            if (indexs[index] != NULL) {
                Status temp(indexs[index]->val, index);
                my_queue.push(temp);
            }
        }

        // 更新临时头指针
        head = head->next;
        return head;
    }
};