Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
解法1: PriorityQueue, O(NlogM)
M是queue的长度,N是所有node的总数。
一个简单的PriorityQueue的应用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
class { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } ListNode dummy = new ListNode(0); ListNode tail = dummy; Queue<ListNode> queue = new PriorityQueue<>((a,b) -> a.val - b.val); for (int i = 0; i < lists.length; i++) { if (lists[i] != null) { queue.offer(lists[i]); } } while (!queue.isEmpty()) { ListNode next = queue.poll(); tail.next = next; tail = tail.next; if (next.next != null) { queue.offer(next.next); } } return dummy.next; } }
|
近期评论