分析

• 本题的考点：归并排序、堆。

• 本题有两种比较经典的解法，这里都讲解一下。

自底向上归并排序

• 类似于归并排序，如下图，这里使用自底向上归并排序，每一行代表当前还剩余多少链表没有被合并，当最终合并成一个链表时，就是答案。这里合并两个链表会用到：Leetcode 0021 合并两个有序链表。

堆（优先队列）

• 使用小顶堆，每次取出堆顶元素，此时一定是最小的元素，放到结果链表中，直到堆为空。这里的难点关键是如何实现堆中放入链表？（其实放入的只是链表的头指针）

代码

• C++

// 自底向上归并排序
class Solution {
public:
    ListNode *merge(ListNode *l1, ListNode *l2) {
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;

        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {

        if (lists.empty()) return NULL;
        for (int step = 1; step < lists.size(); step += step)  // 每次合并的两个链表的索引差值
            for (int i = 0; i + step < lists.size(); i += step + step)  // i 代表两个待合并链表中的第一个
                lists[i] = merge(lists[i], lists[i + step]);
        return lists[0];
    }
};

// 堆
class Solution {
public:
    struct Cmp {
        // STL容器在比较的时候用的是结构体的小括号运算符
        bool operator() (ListNode *a, ListNode *b) {
            return a->val > b->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {

        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;  // 小顶堆
        auto dummy = new ListNode(-1), tail = dummy;
        for (auto l : lists) if (l) heap.push(l);

        while (heap.size()) {
            auto t = heap.top();
            heap.pop();
            tail = tail->next = t;
            if (t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

• Java

// 自底向上归并排序
class Solution {
    // 返回l1和l2合并后链表的头结点
    private ListNode mergeTwoList(ListNode l1, ListNode l2) {

        if (l1 == null) return l2;
        if (l2 == null) return l1;

        if (l1.val < l2.val) {
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoList(l1, l2.next);
            return l2;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0) return null;
        for (int step = 1; step < lists.length; step += step)  // 每次合并的两个链表的索引差值
            for (int i = 0; i + step < lists.length; i += (step + step))  // i 代表两个待合并链表中的第一个
                lists[i] = mergeTwoList(lists[i], lists[i + step]);  // list[i] 和 list[i+step] 进行合并
        return lists[0];
    }
}

// 堆
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {

        Queue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        ListNode dummy = new ListNode(-1), tail = dummy;
        for (ListNode l : lists)
            if (l != null)
                heap.add(l);

        while (!heap.isEmpty()) {
            ListNode t = heap.remove();
            tail = tail.next = t;
            if (t.next != null) heap.add(t.next);
        }
        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为所有链表节点之和。

• 空间复杂度：$O(m)$，m为链表个数。