题解 | #合并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.size() < 1) {
            return null;
        }
        ListNode node1 = lists.get(0);

        for (int i = 1; i < lists.size(); i++) {
            if(node1 == null){
                if(lists.get(i) == null){
                    continue;
                }
                node1 = lists.get(i);
                continue;
            }
           
            node1 = mergeTwoNode(node1, lists.get(i));
        }
        return node1;
    }

    public ListNode mergeTwoNode(ListNode node1, ListNode node2) {
        ListNode lastNode1 = null;
        ListNode curNode1 = node1;
        ListNode curNode2 = node2;
        //算法复杂度 O(n)
        //仅需遍历node1即可
        //先取出链表2当前值，然后去遍历链表1，比对
        while (curNode1 != null) {
            if (curNode2 == null) {
                //链表2插到链表1插完了，停止遍历
                break;
            }
            //当链表2当前值，没有链表1当前值大时
            //将链表2值插入链表1当前值的前面
            //链表1当前值还为此时遍历到的这个值
            //链表2当前值变为，当前值的下一个
            if (curNode1.val > curNode2.val) {
                //把node2这个往前插
                ListNode tmp = curNode2.next;
                if (lastNode1 == null) {
                    //链表2当前值，比链表1的第一个值还要小
                    ListNode tmpForHead = node1;
                    //链表2当前值变为头
                    node1 = curNode2;
                    //链表2下一个变为链表1当前值
                    curNode2.next = tmpForHead;
                } else {
                    //链表1上一个值的下一个为链表2当前值
                    lastNode1.next = curNode2;
                    //链表2下一个为链表1当前值
                    curNode2.next = curNode1;
                }
                //继续从刚插进来的这个值的下一个遍历
                lastNode1 = curNode2;
                curNode1 = curNode2.next;
                curNode2 = tmp;
            } else {
                //继续遍历表1
                lastNode1 = curNode1;
                curNode1 = curNode1.next;
            }
        }

        if(curNode2 != null){
            //链表1遍历完了，链表2中还有数据
            //说明第一个值，比链表1所有值都大
            lastNode1.next = curNode2;
        }
        
        curNode1 = node1;
        
        return node1;
    }
}