精选50题之 23. 合并K个排序链表

短命女 2024-04-18 11:45 58阅读 0赞

### 腾讯精选练习（50 题）之 23. 合并K个排序链表 ###

*   *  原题目链接
     *  直接实现
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式

## [原题目链接][Link 1] ##

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。  
示例:

> 输入:  
> \[  
> 1->4->5,  
> 1->3->4,  
> 2->6  
> \]  
> 输出: 1->1->2->3->4->4->5->6

## 直接实现 ##

上一篇Blog [精选50题之 21. 合并两个有序链表][50_ 21.] 是这道题的简化（特殊）形式。  
所以，第一个思路就是使用分治策略，将**k 个链表合并** 的问题转化成 **合并 2 个链表k-1 次**。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while(l1 && l2)
        {
        
            if(l1 -> val <= l2 -> val)
            {
        
                cur -> next = l1;
                l1 = l1 -> next;
             }
            else
            {
        
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        cur -> next = l1 == NULL ? l2 : l1;
        return head->next;
    }
    class Solution {
        
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
        
            if(lists.size() == 0)
                return {
        };
            else
            {
        
                ListNode* head = new ListNode(0); // 头结点
                ListNode* cur = head;
                cur ->next = lists[0];
                for(int i = 1; i< lists.size(); i++)
                {
        
                    cur->next = mergeTwoLists(head->next, lists[i]);
                }
                return head ->next;
            }
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]  
复杂度分析：

*  时间复杂度：O(kN)，两两比较为O(N)，共比较k次；
 *  空间复杂度：O(1)，除了一个定位用的头结点head，没有引入其他额外的存储空间。

这种实现只能算是完成要求，效果不是很好。  
简单分析不难发现：中间包含大量**重复比较**，特别是lists\[0\]链表中的元素，几乎和其他所有结点都进行了比较。  
Ps：如果使用多线程呢？

## 题目分析 ##

在“敏捷开发”（不假思索）实现之后，发现还是要好好分析题目，同时想好策略在执行。

回顾分治策略，并参考分析  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]

简单说：n个一组（一般n为2），组内求出最优解（本题为排序），得到一级结果，然后n个一级结果，继续组内求最优解…递归直至求出最终结果。

## 解题分析 ##

Ps. 分组不一定要严格向邻元素进行合并（尽管这是最直观的，实现相对复杂），只要有序的，在第一遍是遍历所有元素即可。  
我不会说是因为报错不断，才换的

在实际的 mergeKLists 函数中，当链表数量不为零时：

1.  前一半的第i个链表和后一半的第i个链表合并，此时前一半的链表已合并过一次；
2.  （原前二分之一的）前一半第i个链表和后一半第i个链表合并，这时前一半已合并两次；
3.  （原四分之一的）…
4.  … … …
5.  （原）第一个链表和第二个链表合并…
6.  至此，仅剩下第一个链表，即为所求。

## 代码实现 ##

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while(l1 && l2)
        {
        
            if(l1 -> val <= l2 -> val)
            {
        
                cur -> next = l1;
                l1 = l1 -> next;
             }
            else
            {
        
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        cur -> next = l1 == NULL ? l2 : l1;
        return head->next;
    }
    
    class Solution {
        
    public:
            ListNode* mergeKLists(vector<ListNode*>& lists) {
        
            if(lists.size() == 0)
                return {
        };
            else
            {
        
                int n = lists.size();
                while (n > 1) 
                {
        
                    int k = (n + 1) / 2; //最大间隔
                    for (int i = 0; i < n / 2; i++) 
                    {
        
                        lists[i] = mergeTwoLists(lists[i], lists[i + k]);
                    }
                    n = k; // 减小间隔
                }
                return lists[0];
            }
        }
    };

![在这里插入图片描述][20190906224255927.png]  
复杂度分析：

*  时间复杂度：O(N log K)
 *  空间复杂度：O(1)

真是：算法不规范，做题两行泪?

## 其他方式 ##

也使用优先队列，利用堆栈进行求解。 留个尾巴。  
就酱~

[Link 1]: https://leetcode-cn.com/problems/merge-k-sorted-lists/submissions/
[50_ 21.]: https://blog.csdn.net/weixin_41728431/article/details/100550602
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/23ffaa8e3b9748a2a2583e5fb916c614.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/324db4aa12694ddfa58a9ccb7bfea24b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d344824de98a4a4aa2fc40ce6bf0a6f6.png
[20190906224255927.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1733f1702a524e299081f588d8ffeb51.png