23、Merge k Sorted Lists

题设

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

public ListNode mergeKLists(ListNode[] lists){

要点

• 链表合并
• 迭代
• 归并排序

对已经有序的k个链表进行合并，有两种思路：

1、对lists中的每2个链表进行merge(merge可以直接采用归并排序的merge方法)，形成新的链表；重复此操作，直到链表数组中的元素只有一个。这种迭代的方法最后跑出来的时间较长；

    public ListNode mergeKLists(ListNode[] lists){
        /*
           1、迭代的方法
         */

        /*
        int len = lists.length;
        if(len == 0 || lists == null)
            return null;
        if(len == 1)
            return lists[0];
        System.out.println("len: " + len);
        ListNode[] newList;
        while(len > 1){
            if(len % 2 != 0)
                newList = new ListNode[len / 2 + 1];
            else
                newList = new ListNode[len / 2];
            for(int i = 0;i < newList.length;i++){
                if(i * 2 + 1 < len)
                    newList[i] = mergeForList(lists[i * 2] , lists[i * 2 + 1]);
                else
                    newList[i] = lists[i * 2];
            }

            lists = newList;
            System.out.println(lists.length + "kkk");
            if(len % 2 == 0)
                len /= 2;
            else
                len = len / 2 + 1;
        }
        return lists[0];
    }

2、递归的方法。其实仔细观察可得，对数组中每两个链表进行归并，生成新链表并重复的过程，类似归并排序中递归分解的过程。我们要做的是把一个链表数组递归分解直到每一个链表元素，然后进行merge即可，这其实就是对一系列的有序链表做归并排序(传统的归并排序中，数组内的元素为int，而这里改成了有序链表而已)

    public ListNode mergeKLists(ListNode[] lists){
        /*
            2、递归的方法

            其实仔细观察可得，对数组中每两个链表进行归并，生成新链表并重复的过程，类似归并排序中递归分解的过程
            我们要做的是把一个链表数组递归分解直到每一个链表元素，然后进行merge即可
         */

        int len = lists.length;
        if(len == 0 || lists == null)
            return null;
        if(len == 1)
            return lists[0];
        return mergeSortForKList(lists , 0 , len - 1);
    }

    /*
        k个有序链表的递归分解
        @list：  待合并的有序链表集合
        @low ：  此次分解的低位
        @high：  此次分解的高位

        与归并算法思路相同，先对链表数组进行分解，直到区间内只剩下一个元素，进行merge
     */
    public ListNode mergeSortForKList(ListNode[] list , int low , int high){
        if(low == high)
            return list[low];

        if(low < high){
            int middle = (low + high) >> 1;
            ListNode left = mergeSortForKList(list, low, middle);
            ListNode right = mergeSortForKList(list, middle + 1, high);

            return mergeForList(left, right);
        }

        return null;
    }

    /*
        有序链表的归并算法
        @leftHead： 拆分后左链表头指针；
        @rightHead：拆分后右链表头指针；

        初始两个链表指针leftHead和rightHead都在头部。比较其对应的val值，将值小的接入新的链表，同时移动链表指针
        一个有序链表遍历完成后，需要将另一个链表剩下的元素接入新的链表
    */
    public ListNode mergeForList(ListNode leftHead  , ListNode rightHead){

        // 存储归并后新的有序链表，最后返回newHead.next
        ListNode newHead = new ListNode(-1);
        ListNode tempHead = newHead;

        // 比较val大小，移动链表并更新保存结果的有序链表
        while(leftHead != null && rightHead != null){
            if(leftHead.val < rightHead.val){
                tempHead.next = new ListNode(leftHead.val);
                leftHead = leftHead.next;
                tempHead = tempHead.next;
            }
            else{
                tempHead.next = new ListNode(rightHead.val);
                rightHead = rightHead.next;
                tempHead = tempHead.next;
            }
        }

        // 将未遍历完的链表接入
        if(leftHead == null)
            tempHead.next = rightHead;
        else
            tempHead.next = leftHead;

        // 返回归并后的有序链表
        return newHead.next;

    }