LC23. 合并K个升序链表

LC23. 合并K个升序链表 题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

示例：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路

链表题目多涉及到节点调换、排序，有时需要考虑到头节点的转换问题。
因此做链表相关题目时进行建立带有表头的链表

一行一行合并

最直白的方法：
首先建立一个链表，依次合并lists中第1个链表、第二个链表……
但在做题时不敢使用，因为怕超时（计算错了时间复杂度）。

在此重新计算一下时间复杂度：

    k == lists.length
    0 <= k <= 10^4
    0 <= lists[i].length <= 500

假设数组中每一个链表都按照最大长度k=104来计算。
首先建立一个空链表，然后与第一个链表合并，合并后链表长度为n
然后与第二个链表合并，合并后链表长度变为2n
第i次合并后，链表长度变为in
则第i次合并的时间复杂度应为O((i-1)n)
总共需要合并n次，则总的时间复杂度为0+n+2n+……+kn=k*(0+nk)/2=k2n/2
去掉系数后，时间复杂度为O（k2n），这么计算的话时间是超时的。
但是此时应注意条件中：

    lists[i].length 的总和不超过 10^4

也就是说k*n最大为104，那么k2n就为108，不会出现超时情况。

分治

一行一行合并时间复杂度依然很大，而且每个时间段只合并两个链表太浪费时间了，我们需要提高一下时间利用率。这时可以采用分治思想
通过递归可以很容易的完成上述功能：
通过递归调用将列表中链表分为两个两个一组，合并后回溯，得到大的链表，然后再与其他链表合并后的大链表进行合并，最终得到结果。
注意终止条件！

优先队列

优先队列和上述方法不同，该方法并不是进行合并。而是将所有链表放入一个优先队列（小顶堆）中依次d出。

首先建立一空链表ans建立一个结构体，用于构建优先队列。结构体中应包含指向当前链表节点的节点数值和节点指针将所有链表第一个节点入堆d出最小值，将其节点加入ans中。再将d出的链表节点的下一节点入堆直到堆中没有元素

这种方法实质是根据链表的第一个节点数值进行排序，再依次加入链表中。

代码 一行一行合并

class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        ListNode* ans = nullptr;
        int len = lists.size();
        for(int i=0;ival<=h2->val){
                a->next = h1;
                h1 = h1->next;
            }
            else{
                a->next = h2;
                h2 = h2->next;
            }
            a = a->next;
        }
        a->next = h1? h1:h2;
        return ans->next;
    }
};

分治

class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        return merge(lists, 0, lists.size()-1);
    }
    ListNode* merge(vector lists, int left, int right){
        if(left>right) return nullptr;
        if(left==right) return lists[left];
        if(left==right-1) return mergetwo(lists[left], lists[right]);
        int mid = left +(right-left)/2;
        return mergetwo(merge(lists, left, mid), merge(lists, mid+1, right));
    }
    ListNode* mergetwo(ListNode* h1, ListNode* h2){
        if(!h1||!h2) return h1? h1:h2;
        ListNode ans, *a = &ans;
        while(h1&&h2){
            if(h1->valval){
                a->next = h1;
                h1 = h1->next;
            }
            else{
                a->next = h2;
                h2 = h2->next;
            }
            a = a->next;
        }
        a->next = h1? h1:h2;
        return ans.next;
    }
};

优先队列

class Solution {
public:
    struct story{
        int val;
        ListNode* list;
        bool operator < (const story &compare) const{
            return val > compare.val;
        }
    };
    ListNode* mergeKLists(vector& lists) {
        int len = lists.size();
        priority_queue q;
        ListNode ans, *a = &ans;
        for(auto ls:lists){
            if(ls)
                q.push({ls->val, ls});
        }
        while(!q.empty()){
            story t = q.top();
            q.pop();
            a->next = t.list;
            a = a->next;
            if(t.list->next!=nullptr)
                q.push({t.list->next->val, t.list->next});
        }
        a->next=nullptr;
        return ans.next;
    }
};