23. 合并K个升序链表

Introduction

Question：23. 合并K个升序链表

Analysis

还是比较简单的题目，用最小堆去快速求解 k 个链表头节点中最小的那个，然后将其移动到归并后的链表中，并将新的链表头结点插入堆中。

Implement

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode *p1, ListNode *p2) {
        return p1->val > p2->val;
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
    for(auto p: lists) {
        if (p) q.push(p);
    }
    ListNode node(0);
    ListNode *p = &node;
    while (!q.empty())
    {
        auto temp = q.top(); q.pop();
        p->next = temp;
        if (temp->next) {
            q.push(temp->next);
            temp->next = nullptr;
        }
        p = p->next;
    }
    return node.next;
}

One More Thing