题解 | #合并k个已排序的链表#

链表中的节点每k个一组翻转
合并k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。
示例
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}

方法一 c++ STL

使用STL中的multiset来维护k个值，并且每次只取其中最小的一个存入链表中。当取完最小的那个再将取的那一列的链表弹出最新的值。

代码

ListNode *mergeKLists(vector<ListNode *> &lists) {
        multiset<pair<int, int> > arr;
        int n = lists.size();
        for(int i = 0; i < n; i ++){   
            if(!lists[i]) continue;
            arr.insert({lists[i]->val, i});
            lists[i] = lists[i]->next;
        }
        ListNode* result = new ListNode(0);
        ListNode* head = result;
        while(arr.size()){    //不断的循环判断数组是否为空
            pair<int, int> pp = *arr.begin();
            arr.erase(arr.begin());
            if(!head){
                head = new ListNode(pp.first);
            }else{
                head->next = new ListNode(pp.first);
                head = head->next;
            }
            if(lists[pp.second]){//如果当前取出的元素还有下一个则将下一个的元素补充到数组中
                arr.insert({lists[pp.second]->val, pp.second});
                lists[pp.second] = lists[pp.second]->next;
            }
        }
        return result->next;
    }

时间复杂度 会遍历所有元素n每次会将元素插入set中,所以复杂度为
空间复杂度 multiset中的数据最多只会存入k个

方法二 归并排序

将数组两两进行合并，使用归并的思想

ListNode *mergeKLists(vector<ListNode *> &lists) {
        int size = lists.size();
        if(size == 0) return nullptr;
        if(size == 1) return lists[0];
        return mergeList(lists, 0, size - 1);
    }
    ListNode *mergeList(vector<ListNode *> &lists, int s, int e){
        if(s == e) return lists[s];
        if(s > e) return nullptr;
        auto i = mergeList(lists, s, (s + e) / 2);    //向左走
        auto j = mergeList(lists, (s + e) / 2 + 1, e);    //向右走
        return merge(i, j);
    }
//归并排序
    ListNode *merge(ListNode *a, ListNode *b){ //合并两个
        ListNode *result = new ListNode(0);
        ListNode *now = result;
        while(a && b){
            if(a->val < b->val) {
                now->next = a;
                now = now->next;
                a = a->next;
            }else{
                now->next = b;
                now = now->next;
                b = b->next;
            }
        }
        if(a) now->next = a;
        if(b) now->next = b;
        return result->next;
    }

时间复杂度 归并排序复杂度
空间复杂度 归并排序中合并存储链表最多存储整个链表长度