题目描述：存在k个有序链表，实现多路归并。
思路：与二路归并类似，需要每次从所有头结点挑选最小的连接到结果链表；二路归并直接比较两个链表的头即可，但是K路的话，每次需要比较K个，使用堆或者红黑树会比较好维护，采用PriorityQueue或者TreeSet。
public ListNode mergeKLists(ListNode[] lists) { if(lists==null||lists.length==0){ return null; } ListNode h,p; //创建堆，设置结点比较器 PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { return o1.val-o2.val; } }); //将所有头结点添加到堆 for (ListNode list : lists) { if (list != null) { queue.add(list); } } //有可能list包含空链表，为了第一次poll不报NPE，先检查 if(queue.isEmpty()){ return null; } //比较-摘下-指针后移 h = queue.poll(); p = h; if(p.next!=null){ queue.add(p.next); } while(queue.size()>1){ p.next=queue.poll(); p=p.next; if(p.next!=null){ queue.add(p.next); } } p.next=queue.poll(); return h; }
