（递归）常规解法与分治法

1.常规解法，从头到尾两两组合链表

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size() == 0){
            return null;
        }
        ListNode result = lists.get(0);
        for(int i = 1; i < lists.size(); i++) {
            ListNode temp = lists.get(i);
            result = merge(result, temp);
        }
        return result;
    }

    public ListNode merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        }else {
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }

2.常规解法的改进，运用了分治思想的归并组合链表

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists==null || lists.size()==0) {
            return null;
        }
        return mergeLists(lists, 0, lists.size()-1);
    }
   public ListNode mergeLists(ArrayList<ListNode> lists,int low, int high) {
        if(low >= high) {
            return lists.get(low);
        }
        int mid = low + ((high-low) >> 1);
        ListNode l1 = mergeLists(lists,low,mid);
        ListNode l2 = mergeLists(lists,mid+1,high);
        return merge(l1, l2);
    }
   public ListNode merge(ListNode list1,ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        if(list1.val < list2.val) {
            list1.next = merge(list1.next, list2);
            return list1;
        }else {
            list2.next = merge(list1, list2.next);
            return list2;
        }
    }