题解 | #合并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 ;
        }
        ListNode pre = new ListNode(-1) ;
        ListNode cur = pre ;
        ListNode l_cur = l ;
        ListNode r_cur = r ;
        while(l_cur != null && r_cur != null) {
            if(l_cur.val < r_cur.val) {
                cur.next = new ListNode(l_cur.val) ;
                cur = cur.next ;
                l_cur = l_cur.next ;
            } else {
                cur.next = new ListNode(r_cur.val) ;
                cur = cur.next ;
                r_cur = r_cur.next ;
            }
        }
        while(l_cur != null) {
            cur.next = new ListNode(l_cur.val) ;
            cur = cur.next ;
            l_cur = l_cur.next ;
        }
        while(r_cur != null) {
            cur.next = new ListNode(r_cur.val) ;
            cur = cur.next ;
            r_cur = r_cur.next ;
        }
        return pre.next ;
    }
}