题解 | 合并k个已排序的链表

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <set>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        auto new_H = new ListNode(0);
        ListNode* cur = new_H;
        // // 优先队列写法
        // priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        // for (auto list : lists) {
        //     if (list) pq.push(list);
        // }
        // 多重集写法
        multiset<ListNode*, Compare> ms;
        for (auto list : lists) {
            if (list) ms.insert(list);
        }
        // // 优先队列写法
        // while (!pq.empty()) {
        //     auto less = pq.top();
        //     pq.pop();
        //     if (less->next) pq.push(less->next);
        //     less->next = nullptr;
        //     cur->next = less;
        //     cur = less;
        // }
        // 多重集写法
        while (!ms.empty()) {
            auto less = ms.begin();
            ListNode *tmp = *less; // 存储迭代器内容,因为下面使用迭代器移除元素后less迭代器不再有意义.
            ms.erase(less); // 使用迭代器进行移除,放置将值相同的节点全部移除集合.
            if (tmp->next) ms.insert(tmp->next);
            tmp->next = nullptr;
            cur->next = tmp;
            cur = tmp;
        }
        return new_H->next;
    }
  private:
    struct Compare {
        bool operator()(ListNode* a, ListNode* b) const {
            // return a->val > b->val; // 优先队列"最大"元素在队首(比较器判断为true表示优先级更小)
            return a->val < b->val; // 集合(多重集)"最小"元素在最前面
        }
    };
};

题干分析:

题目要求我们将k个升序链表合并,就是极为明显的题意.

算法思路拆解:

理想状态下我们只需使用k个指针指向对应链表的头部,每次选取这k个节点中值最小的节点将其插入在结果链表尾部并将选中的节点指针移向对应链表下一节点即可.

针对题目要求,我们需要在时间复杂度为O(n log(n))下完成任务.现在我们已知对总计n个节点进行操作时间复杂度为O(n),那么按照我们的思路,在获取k个节点中最小值的过程中时间复杂度最高为O(log(n)).由此我们不难想到至少3种解决方案:

① 采用定制化的优先队列(C++中为class priority_queue<_Tp, _Sequence, _Compare>)针对k个节点指针进行维护,每次弹出堆顶元素(该指针指向的节点值为这k个节点值最小的)并插入该元素的后继指针.

②该方案与上一方案几乎一致,使用定制化的多重集(C++中为class multiset<_Key, _Compare, _Alloc>)进行存储,每次取集合首部元素,使用迭代器进行删除,然后插入该元素后继指针.

③使用分治思想,将这k个链表分为若干两两一组或者单独一组的链表组,各自两两合并成一个链表,之后持续分组合并直至只剩下一个链表

个人开头提供的代码采用的是思路一和思路二,思路三并未真正尝试实现.

复杂度分析:

针对总计n个节点进行操作,时间复杂度为O(n),空间复杂度为O(1);

针对k个链表指针进行维护(空间复杂度为O(k),以下均为时间复杂度):

优先队列方式:每次取出队首元素:O(1);弹出队首元素与新元素入队:O(log(k));

多重集方式:每次取集合首部元素:O(1);插入与删除元素:O(log(k));

∴总时间复杂度为O(nlog(k)),空间复杂度为:O(k).