23. 合并 K 个升序链表

题目链接

解题思路：每次从全局的拿一个最小值出来，每个链表的「头」，都是最小的，所以，我们可以使用一个小根堆（优先级队列），存放每个链表当前的「头」，然后弹出一个全局最小的节点出来，然后把该节点的next放回小根堆，供之后使用。

• 注意，压入小根堆时，要保证不为nullptr。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    struct MyCompare{
        bool operator()(ListNode *node1, ListNode *node2) {
            return node1->val > node2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, MyCompare> que;    // 小根堆
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] != nullptr) {
                que.push(lists[i]);
            }     
        }
        if (que.empty()) {
            return nullptr;
        }
        ListNode *ans = que.top();
        ListNode *cur = ans;
        que.pop();
        if (ans->next != nullptr) {
            que.push(ans->next);
        }
        while(!que.empty()) {
            cur->next = que.top();
            que.pop();
            cur = cur->next;
            if (cur->next != nullptr) {
                que.push(cur->next);
            }
        }
        return ans;
    }
};