题解 | #合并k个已排序的链表#

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0) return null;
        while (lists.size() > 1) {
            if (lists.size() % 2 == 0) {
                ArrayList<ListNode> curList = new ArrayList<>();
                for (int i = 1; i < lists.size() ; i+=2) {
                    curList.add(mergeTwoList(lists.get(i),lists.get(i-1)));
                }
                lists = curList;
            } else {
                ArrayList<ListNode> curList = new ArrayList<>();
                for (int i = 1; i < lists.size() - 1 ; i+=2) {
                    curList.add(mergeTwoList(lists.get(i),lists.get(i-1)));
                }
                curList.add(lists.get(lists.size() - 1));
                lists = curList;
            }
        }
        return lists.get(0);
    }
    public ListNode mergeTwoList(ListNode root1,ListNode root2) {
        ListNode work = new ListNode(-101);
        work.next = null;
        ListNode vHead = work;
        while (root1 != null && root2 != null) {
            if (root1.val >= root2.val) {
                vHead.next = root2;
                root2 = root2.next;
                vHead = vHead.next; 
            } else {
                vHead.next = root1;
                root1 = root1.next;
                vHead = vHead.next;
            }
        }
        while (root1 != null) {
            vHead.next = root1;
            root1 = root1.next;
            vHead = vHead.next;
        }
        while (root2 != null) {
            vHead.next = root2;
            root2 = root2.next;
            vHead = vHead.next;
        }
        return work.next;
    }
}


//分lists的长度奇数和偶数，两两合并