合并k个已排序的链表

合并k个已排序的链表

图解：（归并排序）

alt

思路：

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

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

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

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

对于这k个链表，就相当于上述合并阶段的k个子问题，需要划分为链表数量更少的子问题，直到每一组合并时是两两合并，然后继续往上合并，这个过程基于递归：

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

step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2n/2n/2个链表和右边n/2n/2n/2个链表。 step 2：继续不断递归划分，直到每部分链表数为1. step 3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    //Merge2（）函数进行合并两个区间，传入两个区间表头
    public ListNode Merge2(ListNode pHead1,ListNode pHead2){
        //判断一下，如果一个区间是空，那么就不需要进行合并了，直接返回非空的链表的头结点
        if(pHead1==null){
            return pHead2;
        }
        if(pHead2==null){
            return pHead1;
        }
        //创建一个虚的头结点，设置一个节点cur，取头结点的地址
        ListNode dummynode=new ListNode(0);
        ListNode cur=dummynode;
        //只要两个表为非空，就一直进行判断两种情况 （用归并排序的思想）
        //将两个节点两两比较，把较小的节点连在新的表中,移动对应的头结点为下一个节点
        while(pHead1!=null&&pHead2!=null){
            if(pHead1.val<=pHead2.val){
                cur.next=pHead1;
                pHead1=pHead1.next;
            }else{
                cur.next=pHead2;
                pHead2=pHead2.next;
            }
            //将cur向后移动一个节点
            cur=cur.next;

        }
        //当发现有链表为空的时候，就进行判断，将非空的链表的剩下的节点接到新的链表的后面
        if(pHead1==null){
            cur.next=pHead2;
        }else{
            cur.next=pHead1;
        }
        //返回新形成的链表的头节点:即虚节点的后一个节点
        return dummynode.next;

    }
    //divideMerge函数，传入需要进行分治和合并的序列的区间，传入该区间左右端点
    public ListNode divideMerge(ArrayList<ListNode> lists,int left,int right){
        //如果left>right,那么就表示这个传入的需要进行分治合并的区间的长度为0，那么就直接不用进行分治合并操作，直接返回null
        if(left>right){
            return null;
        }
        //如果发现left==right，就是表示该区间只有一个节点的时候，就表示分治递归（不断划分区间，直到每个区间只有一个节点了），由于对于一个节点，已经是有序的了，就可以直接返回该节点了，用get函数
        else if(left==right){
            return lists.get(left);
        }
        //求出区间的中点：(left+mid)/2
        //递归调用divideMerge函数：就是接着将区间不断划分，直到区间的长度为1，两个区间的端点为[left，mid]和[mid+1,right],注意在划分的过程中如果不能对半划分，就让左区间的长度大于右区间
        //当不断向下递归划分到每个区间的长度为1的时候，就可以合并递归向上两两合并区间了
        int mid=(left+right)/2;
        return Merge2(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));

    }
   //定义一个函数mergeKLists()用于合并k个序列，传入的参数是用ArrayList存的k个序列
   //调用divideMerge函数进行用归并排序，进行分治和合并，返回形成的新的链表的头节点
   //传入的参数是这k个序列的数组，以及这个数组的左右端点
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        return divideMerge(lists,0,lists.size()-1);
    }
}