题解 | #合并k个有序链表（递归+递归）#

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 ;
        return mergeRange(lists , 0 , lists.size() - 1) ;
    }
    
    //将ArrayList<ListNode>从中间分成前后两段，分别对前后两段进行排序列并返回头结点，
    //最后对两条已排序的链表进行合并 O(n*logn)
    public ListNode mergeRange(ArrayList<ListNode> lists , int start , int end) {
        if(start >= end) return lists.get(start) ;
        int mid = start + (end - start) / 2 ;//寻找中点
        ListNode l = mergeRange(lists , start , mid) ;//对前半部分排序
        ListNode r = mergeRange(lists , mid + 1 , end) ;//对后半部分排序
        return merge(l , r) ;//合并两个有序链表
    }
    
    //合并两个有序链表  O(n)
    public ListNode merge(ListNode l , ListNode r) {
        if(l == null) return r ;
        if(r == null) return l ;
        if(l.val < r.val) {
            l.next = merge(l.next , r) ;
            return l ;
        } else {
            r.next = merge(l , r.next) ;
            return r ;
        }
    }
}