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

一.题目描述
NC51合并k个已排序的链表
题目链接:
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=188&&tqId=38611&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
合并k个已排序的链表并将其作为一个已排序的链表返回。
二.算法(顺序合并)
思路:我们可以想到一种最朴素的方法：用一个变量ans来维护以及合并的链表，第i次循环把第i个链表和ans合并。答案保存到ans中。

class Solution {
public:
    //对两个链表进行合并
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a)||(!b)) return a? a : b;
        ListNode head(0), *r=&head;//r是链表插入的尾指针
        ListNode *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {//利用尾插法把数值小的插入
                r->next=aPtr;
                aPtr=aPtr->next;
            } else {
                r->next=bPtr;
                bPtr=bPtr->next;
            }
            r=r->next;
        }
        r->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }
    //遍历对第i个链表进行合并
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

时间复杂度：O(n*n)
空间复杂度：O(n) 需要额外开辟空间
优缺点：时间复杂度高，但是方便实现。

三.算法(分治合并)

思考：要对算法二进行进一步优化很显然再插入过程中我们的复杂度很低很低无法进一步优化，所以我们只能在

对算法二进行优化，用分治的方法进行合并:
(1)将k个链表配对并将铜一对的链表合并。
(2)第一轮合并，k链表被合并成k/2个链表，平均长度为(2n)/k，然后是k/4个链表，k/8个链表等等。
(3)重复这一个过程，直到我们得到了最终的有序链表。

class Solution {
public:
    //对于两个链表的合并
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head(0),*tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }
    //利用分治 对每一小组链表进行合并
    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    //对lists中每一
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

时间复杂度：O(n*log(n))
空间复杂度：O(n)需要额外开辟空间返回链表
优缺点：时间复杂度大大降低，但是由于递归使空间利用率变高