题解 | #合并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) {
        /**
        总体思路：把lists遍历一遍，里面的元素都收集到一个integer数组里面；
        然后把integer数组排序：Collections.sort(arr)
        遍历数组，创建新的链表
        注意：一开始不用考虑lists为空怎么办，就照着代码走，最终返回的就可以了
         */
        
        ArrayList<Integer> numberArr = new ArrayList<Integer>();
        //遍历链表所有元素，得到一个数值数组
        for(int i=0;i<lists.size();i++){
            if(lists.get(i)==null){
                continue;
            }
            ListNode start = lists.get(i);
            numberArr.add(start.val);
            ListNode tail = start;
            while(tail.next!=null){
                tail = tail.next;
                numberArr.add(tail.val);
            }
        }
        Collections.sort(numberArr);
        
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        for(int i=0;i<numberArr.size();i++){
            cur.next = new ListNode(numberArr.get(i));
            cur = cur.next;
        }

        return dummyNode.next;
    }
}