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

这道题一开始就选择了for循环，就是提交的时候超时了，原理就是两两合并，合并使用递归就行。看了别人的，说是用分治算法，就是从中间劈开，左边合并左边的，右边合并右边的，最后两边再合并。也需要使用递归，就是左边不断中劈，直到相邻两个合并。

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
//         if(lists == null || lists.size()==0)return null;
//         if(lists.size()==1)return lists.get(0);
        
//         ListNode node = lists.get(0);
//         for(int i=1;i<lists.size();i++){
//             node=mergeListNode(node,lists.get(i));
//         }
//         return node;
        return mergeList(lists,0,lists.size()-1);
    }
    
    public ListNode mergeList(ArrayList<ListNode> lists ,int left,int right){
          if(left>right)return null;
          if(left==right)return lists.get(left);
          int mid = left+(right-left)/2;
          return mergeListNode(mergeList(lists,left,mid),mergeList(lists,mid+1,right));
    }
    
    public ListNode mergeListNode(ListNode head1 , ListNode head2){
            if(head1==null)return head2;
            if(head2==null)return head1;
            
            if(head1.val<=head2.val){
                    head1.next = mergeListNode(head1.next,head2);
                    return head1;
                }else{
                    head2.next = mergeListNode(head1,head2.next);
                    return head2;
                }
    }
}