LeetCode合并K个排序链表——C

水深无声 2023-06-14 14:53 4阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

## 一、题目描述 ##

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

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

## 二、题解 ##

**（1）纯递归（暴力比较）**  
因为有了两个链表合并的基础，所以我们同理可得，比较每个链表的首数值，那个比较小就拼接到新链表后面，该链表向后移位，递归比较，

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
        
        struct ListNode* temp = NULL;
        int val = INT_MAX;								//最大值 
        int pos = -1;									//位置信息
        for(int i = 0; i < listsSize;i++){
        				//遍历每条链表 
            if(lists[i]){
        								//直到所有遍历完，NULL 结束 
                if(val > lists[i]->val){
        				//判断每条链表当前位置最小值 
                    val = lists[i]->val;
                    pos = i;							//把最小值的下标给 pos 
                }
            }
        }
        if(pos != -1){
        									//有数据返回 
            temp = lists[pos];							//将几条链表中这一位置最小的拼接到 temp 链表中 
            lists[pos] = lists[pos]->next;
            temp->next = mergeKLists(lists,listsSize);	//递归 
        }
        
        return temp;
    }

**（2）分治**  
同理，我们两两比较合并，最后合并成一个

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        
        if(l1==NULL)								
            return l2;
        if(l2==NULL)								
            return l1;
        if(l1->val < l2->val){
        
            l1->next = mergeTwoLists(l1->next,l2);		//递归 
            return l1;
        }else{
        
            l2->next = mergeTwoLists(l1,l2->next);		//递归 
            return l2;
        }
    }
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
        
        struct ListNode *leftList = NULL;
        struct ListNode *rightList = NULL;
    
        if (listsSize < 1) {
        
            return NULL;
        }
        if (listsSize == 1) {
        
            return lists[0];
        }
        if (listsSize == 2) {
        
            return mergeTwoLists(lists[0], lists[1]);	//合并 
        }
        
        leftList = mergeKLists(lists, listsSize / 2);	//递归，一直划分到两两链表 
        rightList = mergeKLists(lists + listsSize / 2, listsSize - listsSize / 2);	//递归，一直划分到两两链表 
        
        return mergeTwoLists(leftList, rightList);		//返回最后两个链表合并结果 
    }

## 三、结果 ##

**（1）纯递归**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

**（2）分治（两两比较）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191119234705749.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191119234546970.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70