题目: 合并K个升序链表

分析

合并K个升序链表和合并两个有序链表的问题类似。

归并法

解决该问题需要两个辅助的数据结构，一个链表 result 存储目标结果，一个长度和链表数量相同的数组 indexTable ，数组中每一位记录对应链表的当前位置，初始阶段数组每一项初始化为对应链表头节点。

从 indexTable 数组中取出每个链表的当前节点，然后比较这些节点的值，将其中最小的数据插入结果链表 result，同时该链表的指针向后移动，并将新的 next 节点存入 indexTable。

循环上述过程，如果某个链表向后移动的过程，next结点为空，后续这些链表的当前节点比较的过程会忽略这些链表。

当所有链表结点在数组中的值都是 Null 的时候，循环结束。

题解

归并法

class Solution {
    public ListNode solute(ListNode[] lists) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {          
                return o1.val-o2.val;
            }
        });

        for(ListNode node:lists ) {
            if(node!=null) {
                queue.add(node);
            }
        }

        while(!queue.isEmpty()) {
            ListNode node =  queue.poll();
            temp.next = node;
            temp = temp.next;
            if(node.next!=null) {
                queue.add(node.next);
            }
        }

        return result.next;
    }
}