23. 合并K个排序链表

题目

• 题号：23
• 难度：困难
• https://leetcode-cn.com/problems/merge-k-sorted-lists/

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例1

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2

输入：lists = []
输出：[]

实现

思路1 暴力求解

第一眼能想到方法：

1. 遍历所有链表中的所有节点，将值存到同一个数组中，花费时间
2. 对数组排序，花费时间
3. 遍历数组并创建一个新的有序链表，花费时间

所以时间复杂度为；
空间复杂度为。

思路2 顺序合并

这里还可以基于Leetcode第21题“合并两个有序链表”的思路。将第一个链表与第二个链表合并到第一个链表，再将第一个链表与第三个链表合并到第一个链表，以此类推，执行多次的“合并两个有序链表”的操作。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        ListNode* head = new ListNode(-1);  // 建立新的头用来保存合并后的链表
        ListNode* tail = head;   // 记录新链表的尾部
        while(a != nullptr && b != nullptr) {
            if(a->val < b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        // 遍历后a和b最多只有一个还未被合并完
        // 直接将链表末尾指向未合并完的链表即可
        if(a == nullptr) {
            tail->next = b;
        } else {
            tail->next = a;
        }
        return head->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *res = lists[0];
        for (int i = 1; i < lists.size(); ++i) {
            res = mergeTwoLists(res, lists[i]);
        }
        return res;
    }
};

时间复杂度：. 假设每个链表的最长长度是 n。第一次合并后的合并链表res长度为2*n，第二次合并res长度为4*n，第i次合并后res长度为2i*n，那么第i次合并的时间代价是. 那么总的时间代价为.
空间复杂度：

思路3 分治合并

基于思路2进行改进，不再按顺序进行合并。
假如有8个链表，则

1. 第一轮：0,1合并到0；2,3合并到2；4,5合并到4；6,7合并到6
2. 第二轮：0,2合并到0；4,6合并到4
3. 第三轮：0,4合并到0
4. 最后返回第0个链表。

/**
 * 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) {
        return merge(lists, 0, lists.size()-1);
    }

    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if(l==r) return lists[l];
        if(l>r) return nullptr;
        int mid = (l+r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid+1, r));
    }

    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        ListNode* head = new ListNode(-1);  // 建立新的头用来保存合并后的链表
        ListNode* tail = head;   // 记录新链表的尾部
        while(a != nullptr && b != nullptr) {
            if(a->val < b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        // 遍历后a和b最多只有一个还未被合并完
        // 直接将链表末尾指向未合并完的链表即可
        if(a == nullptr) {
            tail->next = b;
        } else {
            tail->next = a;
        }
        return head->next;
    }
};

时间复杂度：。第一轮合并组链表，每一组时间为；第二轮合并组链表，每组时间为……所以总的时间复杂度为。
空间复杂度：，递归使用到的栈空间。