[leetcode] Merge K Sorted Lists | k-way merge 轮流出牌算法

Posted by: lexigrey on: August 1, 2013

• In: leetcode
• Leave a Comment

就是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;
}

Tags: easy, list