Problem: 23. 合并 K 个升序链表

题目描述

思路及解法

1.创建虚拟头节点dummy并创建辅助指针p指向dummy；
2.创建最小堆minHeap将每个链表的头节点存入;
3.当minHeap不为空时每次让p指向从最小堆堆顶取出的节点node，若node -next != nullptr则将node -> next也添加到minHeap中；并让p指针后移，最后返回dummy -> next

复杂度

时间复杂度:

$O(nlogk)$;其中$n$为总共的节点个数，$k$为链表的数量

空间复杂度:

$O(n)$

Code

/**
 * 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) {}
 * };
 */
/**
 * An object for comparison
 */
struct compare {
    bool operator() (const ListNode* a, const ListNode* b) {
        return a -> val > b -> val;
    }
};
class Solution {
public:
    /**
     * Merge K ordered linked lists using minimum heap
     *
     * @param lists Set of ordered linked lists
     * @return ListNode*
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        priority_queue<ListNode*, vector<ListNode*>, compare> minHeap;
        for (ListNode* head : lists) {
            if (head != nullptr) {
                minHeap.push(head);
            }
        }

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