题解 | #合并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类
     */
    private ListNode merge(ListNode pHead, ListNode qHead) {
        ListNode dummy = new ListNode(-1), i = pHead, j = qHead, pre = dummy;

        while(i != null && j != null) {
            if(i.val > j.val) {
                pre.next = j;
                j = j.next;
            }
            else {
                pre.next = i;
                i = i.next;
            }
            pre = pre.next;
        }

        if(i != null) pre.next = i;
        if(j != null) pre.next = j;
        return dummy.next;
    }

    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists.size() == 0) return null;
        if(lists.size() == 1) return lists.get(0);
        if(lists.size() == 2) return merge(lists.get(0), lists.get(1));

        int len = lists.size(), mid = len >> 2;
    
        ArrayList<ListNode> arr = new ArrayList();
        ArrayList<ListNode> arr1 = new ArrayList();
        ArrayList<ListNode> res = new ArrayList();


        arr.addAll(lists.subList(0, mid+1));
        arr1.addAll(lists.subList(mid+1, len));

        res.add(mergeKLists(arr));
        res.add(mergeKLists(arr1));

        return mergeKLists(res);
    }
}

归并排序嘛