题解 | #合并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
               // 创建一个新链表
        ListNode newNode = new ListNode(-1);
        // 遍历链表集合
        for (int i = 0; i < lists.size(); i ++) {
            newNode.next = mergerList(lists.get(i), newNode.next);
        }
        return newNode.next;
    }

    public ListNode mergerList(ListNode node1, ListNode node2){
        if(node1 == null) {
            return node2;
        }
         if(node2 == null) {
            return node1;
        }
        // 创建一个新链表
        ListNode node = new ListNode(-1);
        // 新链表的尾节点
        ListNode tail = node;
        while (node1 != null && node2 != null) {
            if(node1.val > node2.val) {
                tail.next = node2;
                node2 = node2.next;
            } else {
                tail.next = node1;
                node1 = node1.next;
            }
             tail = tail.next;
        }
        if(node1 == null) {
            tail.next = node2;
        }

        if(node2 == null) {
            tail.next = node1;
        }
        return node.next;
    }
}