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

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *定义两个链表合并的方法， 然后遍历 list 进行两两合并，也可以采用归并，先两两合并递归，直到只剩下一个链表返回
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        if (null == lists || lists.size() == 0) {
            return null;
        }
        ListNode res = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            res = merge(res, lists.get(i));
        }
        return res;
    }

    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val > node2.val) {
                dummy.next = new ListNode(node2.val);
                node2 = node2.next;
            } else {
                dummy.next = new ListNode(node1.val);
                node1 = node1.next;
            }
            dummy = dummy.next;
        }
        if (null != node1) {
            dummy.next = node1;
        }
        if (null != node2) {
            dummy.next = node2;
        }
        return res.next;
    }
}