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

1、找中间值，把传入的集合链表分为左右俩部分

2、递归二分这个集合，最后，会得到一个元素不能再分。

3、再利用俩个链表顺序合并的方法，把第一个和第二个不能再分的链表合并，并依次三个和第四个合并。。。

4、最后就得到了k个已排序的链表合并结果。

import java.util.*;

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

public class Solution {

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        return mergeKList(lists, 0, lists.size() - 1);
    }

    public ListNode mergeKList(ArrayList<ListNode> lists, int left,int right){
	// 递归终点
        if(left == right){
            return lists.get(left);
        }
        if(left > right){
            return null;
        }
	// 取中间值 >> 1 右移1位表示 / 2^1 
        int mid = left + ((right - left) >> 1);
	// 递归调用到最基础的俩俩合并
	// 分治左右，实现list中的节点元素可以呈树形俩俩合并，实现logn，配合俩俩合并，总时间复杂度nlogn
        return merge(mergeKList(lists,left,mid),mergeKList(lists,mid+1,right));
    }

  
  
    // 俩个链表合并 （基础）
    public ListNode merge(ListNode l1, ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
	// 返回节点
        ListNode dummy = new ListNode(-1);
	// 操作节点
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
	// 补齐剩下未合并完的链
        cur.next = (l1 == null ? l2 : l1);
        return dummy.next;
    }
}