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

合并k个已排序的链表

http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

题目的主要信息：

给定k个排好序的升序链表
将这k个链表合并成一个大的升序链表，并返回这个升序链表的头

方法一：优先队列（小顶堆）

具体做法：

如果是两个有序链表合并，我们可能会利用归并排序合并阶段的思想：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。

其实这道题我们也可以两两比较啊，只要遍历链表数组，取出开头的两个链表，按照上述思路合并，然后新链表再与后一个继续合并，如此循环，知道全部合并完成。但是，这样太浪费时间了。我们就不能准备k个指针，每次比较得出k个指针的最小值吗？

答案是可以的！利用SLT提供的优先队列。优先队列是SLT提供的容器，它参照了堆排序，容器中的元素是有序的，如果是小顶堆，顶部元素就是最小的，每次可以直接取出最小的元素，而每次插入的成本根据堆排序，就是 $O (l o g_{2} n)$ 。也就是每次该容器中有k个元素，我们可以直接拿出最小的元素，再插入下一个元素，相当于每次都是链表的k个指针在比较大小。

step 1：因为SLT提供的优先队列不能直接比较链表值的大小，因此我们要构造一个比较链表值大小的小顶堆，需要重载比较方式。
step 2：先遍历k个链表头，将不是空节点的节点加入优先队列。
step 3：每次依次弹出优先队列中的最小元素，将其连接子啊合并后的链表后面，然后将这个节点在原本链表中的后一个节点（如果不为空的话）加入队列，类似上述双指针的过程。

class Solution {
public:
    struct cmp {
    bool operator()(ListNode* a, ListNode* b) { //重载小顶堆比较方式
        return  a->val > b->val;  
    }
};
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq; //小顶堆
        for(int i = 0; i < lists.size(); i++){ //遍历所有链表第一个元素
            if(lists[i] != NULL) //不为空则加入小顶堆
                pq.push(lists[i]);
        }
        ListNode* res = new ListNode(-1); //加一个表头
        ListNode* head = res;
        while(!pq.empty()){ //直到小顶堆为空
            ListNode* temp = pq.top(); //取出最小的元素
            pq.pop();
            head->next = temp; //连接
            head = head->next;
            if(temp->next != NULL) //每次取出链表的后一个元素加入小顶堆
                pq.push(temp->next);
        }
        return res->next;
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} k)$ ，其中 $n$ 为所有链表的总节点数，最坏需要遍历所有的节点，每次加入优先队列排序需要 $O (l o g_{2} k)$
空间复杂度： $O (k)$ ，优先队列的大小不会超过 $k$

方法二：归并排序思想

具体做法：

既然都是归并排序的思想了，那我们可不可以直接归并的分治来做，而不是顺序遍历合并链表呢？答案也是可以的！

归并排序是什么？简单来说就是将一个数组每次划分成等长的两部分，对两部分进行排序即是子问题。对子问题继续划分，直到子问题只有1个元素。还原的时候呢，将每个子问题和它相邻的另一个子问题利用上述双指针的方式，1个与1个合并成2个，2个与2个合并成4个，因为这每个单独的子问题合并好的都是有序的，直到合并成原本长度的数组。

我们这k个链表，就相当于上述合并阶段的k个子问题，需要两个合并，不断往上，最终合并成完整的一个链表。从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，将这两半子问题合并好了就成了两个有序链表，最后将这两个有序链表合并就成了，依据子问题递归处理：

终止条件： 划分的时候直到左右区间相等或事左边大于右边。
返回值： 每级返回已经合并好的子问题链表。
本级任务： 对半划分，将划分后的子问题合并成新的链表。

合并过程如下所示：

alt

class Solution {
public:
    ListNode* Merge2(ListNode* pHead1, ListNode* pHead2) { //两个有序链表合并
        if(pHead1 == NULL) //一个已经为空了，直接返回另一个
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        ListNode* head = new ListNode(0); //加一个表头
        ListNode* cur = head;
        while(pHead1 && pHead2){ //两个链表都要不为空
            if(pHead1->val <= pHead2->val){ //取较小值的结点
                cur->next = pHead1;
                pHead1 = pHead1->next; //只移动取值的指针
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next; //只移动取值的指针
            }
            cur = cur->next; //指针后移
        }
        if(pHead1) //哪个链表还有剩，直接连在后面
            cur->next = pHead1;
        else
            cur->next = pHead2;
        return head->next; //返回值去掉表头
    }
    
    ListNode* divideMerge(vector<ListNode *> &lists, int left, int right){ //划分合并区间
        if(left > right) 
            return NULL;
        else if(left == right) //中间一个的情况
            return lists[left];
        int mid = (left + right) / 2; //从中间分成两段，再将合并好的两段合并
        return Merge2(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        return divideMerge(lists, 0, lists.size() - 1); //k个链表归并排序
    }
};

复杂度分析：

时间复杂度： $O (n * k)$ ，其中 $n$ 为所有链表的总节点数，最坏情况下每次合并都是 $O (n)$ ，分治为二叉树型递归，每个节点都要使用一次合并，需要合并 $k - 1$ 次
空间复杂度： $O (l o g_{2} k)$ ，最坏情况下递归 $l o g_{2} k$ 层，需要 $l o g_{2} k$ 的递归栈