Leetcode|小根堆|23. 合并K个升序链表

class Solution {
public:
    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        auto prehead = new ListNode();
        auto merge = prehead;
        while (l1 || l2) {
            if (!l1) {
                merge->next = l2;
                break;
            } else if (!l2) {
                merge->next = l1;
                break;
            } else if (l1->val <= l2->val) {
                merge->next = new ListNode(l1->val);
                l1 = l1->next;
            } else if (l1->val > l2->val) {
                merge->next = new ListNode(l2->val);
                l2 = l2->next;
            }
            merge = merge->next;
        }
        return prehead->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        if (lists.size() == 1) return lists[0];
        auto mergeList = merge2Lists(lists[0], lists[1]);
        for (int i = 2; i < lists.size(); i++) 
            mergeList = merge2Lists(mergeList, lists[i]); 
        return mergeList;
    }
};

class cmp {
public:
    bool operator()(const ListNode* a, const ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 1.创建小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        auto reshead = new ListNode();  // 返回结果的链表头
        auto node = reshead;
        // 2.把K个链表的非空头结点依次放入小根堆中
        for (auto& head : lists) 
            if (head) q.push(head);
        // 3.依次取出堆中最小链表节点
        while (!q.empty()) {
            auto tmp = q.top(); q.pop();
            if (tmp->next) q.push(tmp->next);  // 若该节点还有next节点，则压入堆中
            node->next = tmp;    // 堆中最小链表节点加入res
            node = node->next;   // 结果链表指针后移1位
        }
        return reshead->next;
    }
};