【面试经典 150 | 分治】合并 K 个升序链表

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：顺序合并
- 方法二：分治合并
- 方法三：使用优先队列合并
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【链表】【分治】【优先队列】

题目来源

23. 合并 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* merge2Lists(ListNode* list1, ListNode* list2){
        ListNode* dummy = new ListNode(-1);
        ListNode* prev = dummy;

        while(list1 && list2){
            if(list1->val < list2->val){
                prev->next = list1;
                list1 = list1->next;
            }
            else{
                prev->next = list2;
                list2 = list2->next;
            }
            prev = prev->next;
        }
        prev->next = list1 ? list1 : list2;

        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        int i;
        for(i = 0; i < lists.size(); ++i){
            ans = merge2Lists(ans, lists[i]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：渐进的时间复杂度为 $O(k^2n)$ 。分析。

空间复杂度： $O (1)$ 。

方法二：分治合并

用分治的方法进行合并,步骤如下：

将 k 个链表配对并将同一对中的链表合并，
第一轮合并以后， k 个链表被合并成了 $\frac{k}{2}$ 个链表，然后是 $\frac{k}{4}$ 个链表， $\frac{k}{8}$ 个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

代码

/**
 * 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* merge2Lists(ListNode* a, ListNode* b) {
        if (a == nullptr) {
            return b;
        }
        else if (b == nullptr) {
            return a;
        }
        else {
            if (a->val < b->val) {
                a->next = merge2Lists(a->next, b);
                return a;
            }
            else {
                b->next = merge2Lists(a, b->next);
                return b;
            }
        }
        return nullptr;         // 到不了这里
    }


    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 merge2Lists(merge(lists, l, mid), merge(lists, mid+1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

复杂度分析

时间复杂度：渐进的时间复杂度为 $\times logk)$ 。分析。

空间复杂度：递归会使用到 $O(\log k)$ 空间代价的栈空间。

方法三：使用优先队列合并

思路

维护一个优先队列（小顶堆），队列中存放的是 pair<int, ListNode*> 其中第一个元素表示的是节点的值，第二个元素表示该节点，优先队列是关于 节点的值 的优先队列。优先队列中也可以放置封装了节点的值和节点的结构体。小顶堆可以保证每次出队的都是队列中的最小元素，然后将出队的最小元素连接到链表中。

代码

/**
 * 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:
    struct Status {
        int val;
        ListNode *node;
        bool operator < (const Status& rhs) const {
            return val > rhs.val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Status> que;
        for (auto node : lists) {
            if (node) {
                que.push({node->val, node});
            }
        }

        ListNode head, *tail = &head;           // 见笔记中代码理解

        while (!que.empty()) {
            auto f = que.top(); que.pop();
            tail->next = f.node;
            tail = tail->next;
            if (f.node->next) {
                que.push({f.node->next->val, f.node->next});
            }
        }
        return head.next;
    }
};

理解 ListNode head, *tail = &head;

head 初始化为一个空节点，最后 head.next 指向的是合并后链表的头结点。通过 tail 指针来帮助 head.next 指向合并后链表的头节点。

tail 是一个指针，初始化指向的是 head。在第一次为 tail 建立后继节点时，就将捆绑的 head 也指向了一个节点（就是合并链表后的头节点），接着通过 tail = tail->next 操作将 tail 指向了新的节点，也就切断了 tail 与 head 的联系。最后返回合并后的链表头节点为 head->next。

复杂度分析

时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 $O (l o g k)$ ，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 $\times \log k)$ 。