Leetcode 23

题目要求

给定K个升序链表，将K个链表合并为一个升序的链表

核心算法和原理

• 类比合并两个链表：通过对比两个链表上的指针来判断min(nodeA→val, nodeB → val)，将其加入到result中并移动指针一位，合并K个链表也类似；

• 判断min可以使用最小堆来快速实现：将K个链表加入最小堆中，然后每次把top的node提出来加入result，让这个node下移一位，再此加入这个最小堆，直至最小堆为空

• 时间复杂度：假设总共有N个node，最小堆里最多有K个元素，push的时间复杂度为O(logK)，pop和top为O(1)，总共要push N次，故总时间复杂度为O(NlogK)

代码

/**
 * 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:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
	      std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
        ListNode* dummy = new ListNode(-1);
        ListNode* curNode = dummy;
        auto cmp =  [](ListNode* a, ListNode* b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>pq(cmp);
        for (auto head : lists) {
            if (head != nullptr)
                pq.push(head);
        }

        while(!pq.empty()) {
            ListNode* node = pq.top();
            if (node == nullptr) {
                break;
            }
            pq.pop();
            curNode -> next = node;
            curNode = curNode -> next;
            if (node -> next != nullptr) {
                pq.push(node -> next);
            }
        }
        curNode->next = nullptr;
        return dummy -> next;
    }
};