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

归并排序，直接上代码

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //预处理，删除空的node
        Iterator<ListNode> it = lists.iterator();
        while(it.hasNext()){
            ListNode node = it.next();
            if(node==null){
                it.remove();
            }
        }
        //如果处理过后还是为空，则返回null
        if(lists.size()==0){
            return null;
        }
        //新链表的头
        ListNode newHead = null;
        newHead = findMin(lists);
        //指针
        ListNode cur =newHead;
        while(lists.size()>0){//如果lists的大小大于0则循环进行
            cur.next = findMin(lists);//指针的下一个为lists中的最小的node
            cur = cur.next;//迭代指针
        }
        return newHead;
    }

    //找到lists中所有node头结点最小的node，同时将其移除
    ListNode findMin(ArrayList<ListNode> lists){
        ListNode min = null;
        //最小值
        int minVal = Integer.MAX_VALUE;
        //下标
        int idx = 0;
        //遍历lists
        for(int i=0;i<lists.size();i++){
            ListNode root = lists.get(i);
            if(root!=null){  
               if(root.val<minVal){
                   minVal = root.val;
                   min = root;
                   idx = i;
               }
            }
        }
        //先将其从lists中移除
        lists.remove(idx);
        //如果移除的node还有next则将next加入list的原位置，否则直接删除
        if(min.next!=null){
            lists.add(idx,min.next);
        }
        return min;
    }
}