题解 | #优先级队列写合并k个已排序的链表#
合并k个已排序的链表
http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
通过队列来做;
用容量为K的最小堆优先队列,把链表的头结点都放进去,然后出队当前优先队列中最小的,挂上链表,,然后让出队的那个节点的下一个入队,再出队当前优先队列中最小的,直到优先队列为空。
public ListNode mergeKLists(List<ListNode> lists) { if(lists == null || lists.size() == 0) return null; ListNode temp = new ListNode(-1); ListNode cur = temp; PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>(){ public int compare(ListNode o1,ListNode o2){ return o1.val -o2.val; } }); for (ListNode list:lists){ if(list == null) continue; pq.add(list); } while(!pq.isEmpty()){ ListNode pre = pq.poll(); cur.next = pre; cur = cur.next; if(pre.next != null){ pq.add(pre.next); } } return temp.next; }