0023. 合并 K 个升序链表

[utterances-bot]

0023. 合并K个升序链表 | 算法通关手册

23. 合并K个升序链表 # 标签：链表、分治、堆（优先队列）、归并排序 难度：困难 题目大意 # 给定一个链表数组，每个链表都已经按照升序排列。 要求：将所有

https://algo.itcharge.cn/Solutions/0001-0099/merge-k-sorted-lists/

[S1mpleBug]

附上C++代码

merge操作等同于实现两个有序链表的合并，mergeSort等同于划分vector中的多组链表，注意递归退出条件。

class Solution {
public:
    ListNode *mergeSort(vector<ListNode *> &lists, int l, int r) {
        if(l == r) return lists[l];
        int mid = l+((r-l)>>1);
        ListNode *left = mergeSort(lists, l, mid);
        ListNode *right = mergeSort(lists, mid+1, r);
        return merge(left, right);
    }

    ListNode *merge(ListNode *lists1, ListNode *lists2) {
        ListNode *node = new ListNode(0);
        ListNode *tmp = node;
        while(lists1 && lists2) {
            if(lists1->val <= lists2->val) {
                tmp->next = lists1;
                lists1 = lists1->next;
            } else {
                tmp->next = lists2;
                lists2 = lists2->next;
            }
            tmp = tmp->next;
        }
        if(lists1) tmp->next = lists1;
        if(lists2) tmp->next = lists2;
        return node->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if(n == 0) return nullptr;
        if(n == 1) return lists[0];
        return mergeSort(lists, 0, n-1);
    }
};