[LC]23.合并k个升序链表

题目

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

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

分析

分治

将k个链表两两配对合并为一个更长的有序链表，将原问题规约为规模更小的子问题。

代码

/**
 * 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 *mergeTwoLists(ListNode *h1, ListNode *h2)
    {
        if (h1 == nullptr || h2 == nullptr) return h1 ? h1 : h2;
        ListNode dummy, *tail = &dummy;
        while (h1 && h2)
        {
            if (h1->val <= h2->val)
            {
                tail->next = h1;
                h1 = h1->next;
            }
            else
            {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        tail->next = h1 ? h1 : h2;
        return dummy.next;
    }
    // [l,r]
    ListNode *merge(vector<ListNode*> &lists, int l, int r)
    {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = l + ((r - l) >> 1);
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

注意39行计算中位数的方法，通常的方法是 (l + r) / 2 ，这种方法在l和r过大的时候可能会发生溢出的问题，因此更好的方法是 l + ((r - l) >> 1) ，需要特别注意的是注意后面的括号不要省略，因为加法的优先级更高。

时间复杂度

递推方程：$W(k) = W(k/2) + k/2 \times 2n, 其中n为每个链表的平均长度.$

解这个递推方程可以得到$W(k) = O(knlogk).$

优先队列

另一种思路是将k个链表的头结点通过一个小顶堆来维护，每次取出最小的结点，然后将该结点下一个结点重新插入小顶堆中。

代码

/**
 * 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) {
        auto cmp = [](const ListNode *lhs, const ListNode *rhs)
        {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        ListNode dummy, *tail = &dummy;
        for (auto list : lists) 
            if (list) pq.push(list);
        while (!pq.empty())
        {
            tail->next = pq.top(); pq.pop();
            tail = tail->next;
            if (tail->next) pq.push(tail->next);
        }
        return dummy.next;
    }
};

时间复杂度

小顶堆中插入和删除操作的时间复杂度都是$O(logk)$，所有结点都需要进队一次，出队一次，因此算法的时间复杂度是$O(knlogk)$，和分治算法的时间复杂度一样。