合并 K 个升序链表 C++

���你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

方法1：堆

先把每个链表数组的头节点入堆（小顶堆/小根堆），然后出堆，出堆之后，哪个数组的头节点先出堆，就要补充哪个数组的头节点。就这样一直补充下去，知道所有的节点被遍历完。

class Solution {public:    ListNode* mergeKLists(vector& lists) {        auto cmp = [](const ListNode *a, const ListNode *b){            return a->val > b->val;        };        priority_queue pq;                for (auto head: lists)            if (head) pq.push(head);        auto dummy = new ListNode();        auto cur = dummy;        while (!pq.empty()){            auto node = pq.top();            pq.pop();            if (node->next)                pq.push(node->next);            cur->next = node;            cur = cur->next;        }        return dummy->next;    }};

priority_queue的语法需要注意，首先构建了一个lambda函数。

方法2，归并

把链表数组均分，直到剩余1个数组，分开之后合并，利用基础的合并两个有序链表的算法，再合并上去。

class Solution {    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {        auto dummy = new ListNode(); // 用哨兵节点简化代码逻辑        auto cur = dummy; // cur 指向新链表的末尾        while (list1 && list2) {            if (list1->val val) {                cur->next = list1; // 把 list1 加到新链表中                list1 = list1->next;            } else { // 注：相等的情况加哪个节点都是可以的                cur->next = list2; // 把 list2 加到新链表中                list2 = list2->next;            }            cur = cur->next;        }        cur->next = list1 ? list1 : list2; // 拼接剩余链表        return dummy->next;    }    // 合并从 lists[i] 到 lists[j-1] 的链表    ListNode *mergeKLists(vector &lists, int i, int j) {        int m = j - i;        if (m == 0) return nullptr; // 注意输入的 lists 可能是空的        if (m == 1) return lists[i]; // 无需合并，直接返回        auto left = mergeKLists(lists, i, i + m / 2); // 合并左半部分        auto right = mergeKLists(lists, i + m / 2, j); // 合并右半部分        return mergeTwoLists(left, right); // 最后把左半和右半合并    }public:    ListNode *mergeKLists(vector &lists) {        return mergeKLists(lists, 0, lists.size());    }};