合并 k 个已排序的链表

2023-07-30
四川
本文字数：3394 字
阅读完需：约 11 分钟

前言：

今天给大家分享一道面试中常见的题目——合并 K 个升序链表，我会用暴力和分治两钟方法去求解这道题目，通过动图展示问题求解的全过程。这里提醒大家，画图是我们求解复杂问题的有效手段，有时可以起到事半功倍的效果，各位小伙伴在做题的过程中如果遇到麻烦，不妨动手画画图哟。

题目描述：

合并 K 个升序的链表并将结果作为一个升序的链表返回其头节点。例如：

输入：[{1,2},{1,4,5},{6},{2,3,5}]
输出：{1,1,2,2,3,4,5,5,6}

思路一：暴力求解法

首先根据题目的描述，画出如下模拟图。

第一步：确定合并后链表的头节点 rhead

从上图中可以看出：lists中存放是每个链表的头节点，那合并后链表的头节点一定是这四个头结点中最小的那个，因此我们只需要遍历lists就可以找到最小的头节点，然后把它赋值给rhead，执行完第一步得到的结果如下图，用黄色标注已经排好序的节点：

第二步：选择次小的进行尾插

如上图，接下来我们需要在所有蓝色节点中选出最小的一个尾插到rhead指向的链表，因此我们再定义一个rtail指向合并后链表的最后一个节点。但是我们发现如果按照上图的结构，直接从四个蓝色节点里面选出最小的，显然十分困难，因为第一个链表中待比较的节点不再数组中。如果向第一步那样，所有的节点都在数组中，那选出最小的节点简直是易如反掌，只需要遍历一遍数组即可。因为lists数组中存的永远都是头节点，所以这里我们直接修改第一个链表的头节点即可，通过lists[0] = lists[0]->next就可以实现。修改后的结构如下图所示：

此时所有待比较的节点都来到了数组中，和第一步的逻辑一样，只需要遍历一遍数组就可以找到最小的节点，找到后尾插到rhead指向的链表。如下图，其中黄色节点是已排好序的节点，蓝色节点是待比较的节点。

总体逻辑就是这样，接下来循环执行第二步，找到次小的进行尾插，直到数组中的所有节点都为空，此时说明数组中的所有链表都已经排好序了，返回rhead即可。总的过程动图如下：

🐼代码实现：

class Solution {public:    ListNode* mergeKLists(vector<ListNode*>& lists) {        ListNode* rhead = nullptr;//定义合并后链表的头节点        ListNode* rtail = nullptr;//定义合并后链表的尾结点        while (true)        {            int minIndex = -1;//定义lists数组中最小节点下标，最初等于-1，（下简称最小位置）            int i = lists.size();//            while (i--)            {                if (lists[i] != nullptr)//首先判断数组当前位置的节点是否为空                {                    //当前节点不为空再进来                    if (minIndex == -1)//判断最小位置是否是-1，如果是就直接把当前位置赋值给minIndex                    {                        minIndex = i;                    }                    else if (lists[i]->val < lists[minIndex]->val)//如果minIndex不为-1，则用数组当前位置节点的val与记录的最小位置上节点的val进行比较                    {                        minIndex = i;//如果当前节点的val值更小，那就更新minIndex                    }                }            }            if (minIndex == -1)//遍历完一遍数组如果minIndex的值还是-1，说明当前数组中的所有节点全是空            {                return rhead;//此时说明所有链表已经合并完成，可以返回头节点            }            if (rhead == nullptr)//确定新链表的头节点            {                rhead = rtail = lists[minIndex];            }            else//之后每找出一个最小的节点，进行尾插即可            {                rtail->next = lists[minIndex];                rtail = rtail->next;            }            lists[minIndex] = lists[minIndex]->next;//最小的节点已经尾插到新链表，因此要对最小位置上的节点更新        }    }};

复制代码

上面代码中需要注意的有：minIndex是用来记录lists中最小节点的位置，它的初始值必须是-1，不能是0或其他数字，因为我们不知道 0 或其他位置上的节点是否为空。还有需要注意的地方是，每当遍历到一个节点，首先要判断是否为nullptr，当不为空的时候再进行比较，避免出现空指针问题，其次要判断minIndex当前是否为-1，如果是-1，就不用比较，直接把当前位置赋值给minIndex即可，因为如果当minIndex == -1 的时候进行比较，会导致数组越界。

思路二：分治归并法

分治即“分而治之”，“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的问题，子问题继续按照这样划分，直到问题可以被轻易解决；“治”指的是将子问题单独进行处理。经过分治后的子问题，需要将解进行合并，也就是所谓的“归并”，这样才能得到原问题的解，因此整个分支过程经常采用递归来实现。

针对这道题目来说，我们比较熟悉的是合并两个有序链表，因此我们就可以把合并 K 个有序链表的问题，划分成合并两个有序链表的问题，具体过程我通过动图来给大家演示，其中相同的颜色代表一个子问题。

通过上面的动图我们可以发现，当子问题被分解到只剩一个链表的时候，就无法再进行分解，此时就需要返回了，其实这就是递归的终止条件，也就是当left == right的时候就只剩一个链表，此时就应该返回了，返回的结果就是这一个链表。等左右区间各返回一个链表，此时就要开始对这两个链表进行合并，从而得到一个新的有序链表，再把这个链表作为子问题的处理结果进行返回。这其实很像二叉树的后序遍历，如此循环往复，直到最终的大问题被解决。

🐼代码实现：

class Solution {public:    ListNode* mergeKLists(vector<ListNode*>& lists) {        return dividemerge(lists, 0, lists.size() - 1);    }private:    ListNode* dividemerge(vector<ListNode*>& lists, int left, int right)    {        if (left > right)        {            return nullptr;        }        else if (left == right)        {            return lists[left];        }        int mid = left + (right - left) / 2;        //分治        ListNode* head1 = dividemerge(lists, left, mid);        ListNode* head2 = dividemerge(lists, mid + 1, right);        //对子问题处理        return Merge(head1, head2);    }private:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)//合并两个有序链表    {        if (pHead1 == nullptr)        {            return pHead2;        }        if (pHead2 == nullptr)        {            return pHead1;        }        ListNode* pHeadret, * tail;        if (pHead1->val < pHead2->val)        {            pHeadret = tail = pHead1;            pHead1 = pHead1->next;        }        else        {            pHeadret = tail = pHead2;            pHead2 = pHead2->next;        }        while (pHead1 != nullptr && pHead2 != nullptr)        {            if (pHead1->val < pHead2->val)            {                tail->next = pHead1;                pHead1 = pHead1->next;            }            else            {                tail->next = pHead2;                pHead2 = pHead2->next;            }            tail = tail->next;        }        if (pHead2 != nullptr)        {            tail->next = pHead2;        }        if (pHead1 != nullptr)        {            tail->next = pHead1;        }        return pHeadret;    }};

复制代码

分治的大思想，其实就体现在下面三行代码中：

//分治ListNode* head1 = dividemerge(lists, left, mid);        ListNode* head2 = dividemerge(lists, mid + 1, right);
//对子问题处理        return Merge(head1, head2);

复制代码

我们只需要知道，前两行代码将一个大问题进行分解，得到的两个子问题，并且经过dividemerge函数把这两个子问题都处理好了，并且得到了两个结果，针对本题，就是得到了两个有序的链表，分别是head1和head2，然后我们只需要对这两个链表进行合并就可以完成题目的要求，也就是第三行代码实现的功能。这就是分治的思想。