Lexi's Leetcode solutions

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

Posted 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;
}
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,235 hits
August 2013
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  
%d bloggers like this: