leetcode23合并K个升序链表

叁歲伎倆 2022-10-06 09:54 178阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
思路：

1.  首先构造合并两个有序链表的方法
2.  接下进行分治递归调用的操作，不停的分解划分成两个一组进行排序，然后再进行合并  
    （1）`lists.size()==0;return null;`  
    （2）`lists.size()==1;return lists[0];`  
    （3）`lists.size()==2;return mergetwo(lists[0],lists[1]);`  
    （4）将lists一分为二，两部分分别进行`mergeklists()`  
    （5）将一分为二的list进行`mergetwo`合并

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]

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) { }
    };
    
    ListNode* mergetwo(ListNode *head1,ListNode*head2){ 
        ListNode* new_head = new ListNode();
        ListNode *p =new_head;
        while (head1&&head2)
        { 
            if(head1->val<head2->val){ 
                p->next=head1;
                head1=head1->next;
            }
            else{ 
                p->next=head2;
                head2=head2->next;
            }
            p=p->next;
        }
        if(head1)
            p->next=head1;
        if(head2)
            p->next=head2;
        
        return new_head->next;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists){ 
        if (lists.size()==0)
        { 
            return NULL;
        }
        if (lists.size()==1)
        { 
            return lists[0];
        }
        if(lists.size()==2){ 
            return mergetwo(lists[0],lists[1]);
        }
        vector<ListNode*> temp1;
        vector<ListNode*> temp2;
        int i=0;
        for(;i<(lists.size()/2);i++)
            temp1.push_back(lists[i]);
        for(;i<lists.size();i++)
            temp2.push_back(lists[i]);
        
        ListNode* l1 = mergeKLists(temp1);
        ListNode* l2 = mergeKLists(temp2);
        return mergetwo(l1,l2);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/dda881c7382b42bb8cfa3f43b816c722.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/54a114864c214c599729a7ba503e6b44.png