2018-11-25 22:58:52
问题描述:
问题求解:
本题可以使用优先队列高效的进行求解,整体的时间复杂度为O(nlogk)。
public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } }); for (ListNode ln : lists) if (ln != null) pq.add(ln); while (!pq.isEmpty()) { cur.next = pq.poll(); cur = cur.next; if (cur.next != null) pq.add(cur.next); } return dummy.next; }