[leetcode] Merge K Sorted Lists | k-way merge 轮流出牌算法
Posted by: lexigrey on: August 1, 2013
就是merge sort那个n-way merge,轮流出牌。这个题的重点是要用heap,这样每次新加一个元素的时侯能很快的找到新的min。还有,这是第一次真的implement priority queue,需要自己写comparator(小于号说明是MinHeap)。
public ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode result = null; ListNode curr = result; Comparator<ListNode> comp = new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return a.val - b.val; } }; PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.size(), comp); for (int i = 0; i < lists.size(); i++) { ListNode currHead = lists.get(i); if (currHead != null) minHeap.add(currHead); } while (!minHeap.isEmpty()) { ListNode smallest = minHeap.poll(); if (result == null) { result = smallest; curr = result; } else { curr.next = smallest; curr = curr.next; } ListNode nextEnqueue = smallest.next; if (nextEnqueue != null) minHeap.add(nextEnqueue); } return result; }
Leave a Reply