题解 | #合并k个已排序的链表# 分治策略+多路递归

import java.util.*;

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

public class Solution {
    /**
     * 思路：分治策略+多路递归
     *		将链表集合根据索引拆分两部分，递归进行不断拆分两部分链表，直到拆分到两部分都只剩一个链表
	 *		这时可以合并两个链表，最后返回的就是多个链表合并后的结果
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if(lists.size() == 0){
            return null;
        }
        return split(lists,0,lists.size() - 1 );
    }
    public ListNode split(ArrayList<ListNode> lists, int i, int j){
	  	//治
        if(i == j){
            return lists.get(i);
        }
	  	//分
        int m = (i + j) >>> 1; //中间索引
        ListNode p1 = split(lists,i,m);
        ListNode p2 = split(lists,m+1,j);
	  	//合
        return merge(p1,p2);

    }
  	//合并两个链表
    public ListNode merge(ListNode p1, ListNode p2){
        if(p1 == null){
            return p2;
        }
        if(p2 == null){
            return p1;
        }
        if(p1.val < p2.val){
            p1.next = merge(p1.next,p2);
            return p1;
        }else{
            p2.next = merge(p1,p2.next);
            return p2;
        }
    }
}