题解 | 合并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) {
        // write code here
        if(lists==null || lists.size()==0) return null;
        return mergeSort(lists, 0, lists.size()-1);//对n个链表进行分治法
    }
    private ListNode mergeSort(ArrayList<ListNode> lists, int l, int r){
        if(l==r) return lists.get(l);
        int mid = (l+r-1)/2;
        ListNode left = mergeSort(lists, l, mid);
        ListNode right = mergeSort(lists, mid+1, r);
        return listSort(left, right);
    }
    private ListNode listSort(ListNode A, ListNode B){
        ListNode a = A;
        ListNode b = B;
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        if(a==null) return b;
        if(b==null) return a;
        while(a!=null && b!=null){
            if(a.val<=b.val){
                tail.next = a;
                a = a.next;
            }
            else{
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        if(a==null) tail.next = b;
        if(b==null) tail.next = a;
        return dummy.next;
    }

}