Problem23

    public ListNode mergeKLists(ListNode[] lNodes) {
//        递归，耗时很长，核心在于两个ListNode的递归比较
//        if (lNodes.length == 0) return null;
//        if (lNodes.length == 1) return lNodes[0];
//        ListNode merged = lNodes[0];
//        for (int i = 1; i < lNodes.length; i++) {
//            merged = mergeTwoList(merged,lNodes[i]);
//        }
//        return merged;

        //使用PriorityQueue,非原来的queue先进先出
        //元素小的，优先级高，越先出
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (ListNode lNode : lNodes) {
            while(lNode !=null){
                pq.add(lNode.val);
                lNode = lNode.next;
            }
        }
        ListNode mergedNode = new ListNode(-1);
        ListNode tempNode = mergedNode;
        while(!pq.isEmpty()){
            tempNode.next = new ListNode(pq.remove());
            tempNode = tempNode.next;
        }
        return mergedNode.next;
    }

    private ListNode mergeTwoList(ListNode merged, ListNode lNode) {
        if (merged == null || lNode == null) return lNode == null ? merged : lNode;
        if (merged.val < lNode.val) {
            merged.next = mergeTwoList(merged.next, lNode);
            return merged;
        } else {
            lNode.next = mergeTwoList(merged, lNode.next);
            return lNode;
        }
    }