leetcode23. 合并K个排序链表

1. 题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[  1->4->5,  1->3->4,  2->6]输出: 1->1->2->3->4->4->5->6来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

2. 解题思路

3. 测试结果

解法一、顺序合并

解法二、分治合并

4. 顺序合并

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {    if (!l1)        return l2;    if (!l2)        return l1;    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)), * tail = head;    while (l1 && l2) {        if (l1->val < l2->val) {            tail->next = l1;            l1 = l1->next;        }        else {            tail->next = l2;            l2 = l2->next;        }        tail = tail->next;    }    if (l1) tail->next = l1;    else if (l2) tail->next = l2;    tail = head;    head = head->next;    free(tail);    return head;}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {    if (listsSize == 0)        return NULL;    struct ListNode* res = *lists;    for (int i = 1; i < listsSize; i++)    {        if(lists[i] != NULL)            res = mergeTwoLists(res, lists[i]);    }    return res;}

5. 分治合并

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {    if ((!l1) || (!l2)) return l1 ? l1 : l2;    struct ListNode head;    head.next = NULL;    struct ListNode* tail = &head;    while (l1 && l2) {        if (l1->val < l2->val) {            tail->next = l1;            l1 = l1->next;        }        else {            tail->next = l2;            l2 = l2->next;        }        tail = tail->next;    }    tail->next = l1 ? l1 : l2;    return head.next;}struct ListNode* merge(struct ListNode** lists, int left, int right) {    if (left == right)        return lists[left];    if (left > right)        return NULL;    int mid = (left + right) >> 1;    struct ListNode* p1 = merge(lists, left, mid);    struct ListNode* p2 = merge(lists, mid + 1, right);    return mergeTwoLists(p1, p2);}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {    if (listsSize == 0)        return NULL;    return merge(lists, 0, listsSize - 1);}

6. 复杂度分析

解法一、顺序合并
时间复杂度：O(n*n)
空间复杂度：O(1)
解法二、分治合并
时间复杂度：O(nlogn)
空间复杂度：O(1)