2014年4月10日 星期四

[LeetCode] Merge k Sorted Lists

Problem:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:O(n)


public class Solution {
  public ListNode mergeKLists(ArrayList<ListNode> lists) {
    if (lists.size() == 0)
      return null;
 
    Queue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),
      new Comparator<ListNode>() {
        public int compare(ListNode a, ListNode b) {
          return (a.val-b.val);
        }
      }
    );
 
    for (ListNode list : lists) {
      if (list != null)
      q.add(list);
    }
 
    ListNode head = new ListNode(0);
    ListNode prev = head;
 
    while (q.size() > 0) {
      ListNode temp = q.poll();
      prev.next = temp;
 
      if (temp.next != null)
        q.add(temp.next);
    
      prev = prev.next;
    }
    return head.next;
  }
}

Key concept: Use PriorityQueue or heap to help get the smallest list. Use dummy node to avoid null.

沒有留言:

張貼留言