题解 | #合并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类
     */
    class ConNodeList{
        ListNode listnode;
        int team;
        ConNodeList(ListNode listnode, int team){
            this.listnode=listnode;
            this.team = team;
        }
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists.size()==1){
            return lists.get(0);
        }
        if(lists.size()==0){
            return null;
        }

        PriorityQueue<ConNodeList> queue = new PriorityQueue<ConNodeList>(lists.size(), new Comparator(){
            public int compare(Object l1, Object l2){
                ConNodeList l11 = (ConNodeList)l1;
                ConNodeList l22 = (ConNodeList)l2;
                if(l11.listnode.val< l22.listnode.val){
                    return -1;
                }else{
                    return 1;
                }
            }
        });
        int times=0;
        int len = lists.size();
        for(int i=0;i<len;i++){
            if(lists.get(i)!=null){
                queue.add(new ConNodeList(lists.get(i),i));
                lists.set(i,lists.get(i).next);
            }else{
                times++;
            }
        }
        
        ListNode start = new ListNode(-1),pointer=start;
        ConNodeList temp;
        int teamTemp;
        while(times!=len){
            temp=queue.poll();
            pointer.next = temp.listnode;
            
            teamTemp = temp.team;
            pointer = pointer.next;
            System.out.println(pointer.val);
            if(lists.get(teamTemp)!=null){
                queue.add(new ConNodeList(lists.get(teamTemp),teamTemp));
                lists.set(teamTemp,lists.get(teamTemp).next);
            }else{
                times++;
            }

        }
        return start.next;
    }






}

priorityQueue是一个堆，我又菜，不会写堆，因此利用这个队列来实现堆。

对于菜鸟的难点在于，不知道PriorityQueue的存在，以及重写PriorityQueue compare方法。