Merge k Sorted Lists

思路：
有多种解法，最有价值的就是用heap和分治法。

解法一：
heap

把所有listnode放到heap里面。然后挨个从heap里面取，这样可以保证每次取的都是最小值。连到result list上。如果heap.poll().next != null，把heap.poll().next放进heap里面。
代码如下：

 /**  
  * Definition for ListNode.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int val) {  
  *     this.val = val;  
  *     this.next = null;  
  *   }  
  * }  
  */   
 public class Solution {  
   /**  
    * @param lists: a list of ListNode  
    * @return: The head of one sorted list.  
    */  
   public ListNode mergeKLists(List<ListNode> lists) {   
     // write your code here  
     if(lists.size() == 0 || lists == null )  
     {  
       return null;  
     }  
     Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>() {  
       public int compare(ListNode a, ListNode b) {  
         return a.val - b.val;  
       }  
     });  
     // initialize heap  
     for(ListNode n: lists) {  
       if(n != null) {  
         heap.add(n);    
       }  
     }  
     ListNode dummy = new ListNode(0);  
     ListNode tail = dummy;  
     while(!heap.isEmpty()) {  
       ListNode current = heap.poll();  
       tail.next = current;  
       tail = current;  
       if(current.next != null) {  
         heap.add(current.next);  
       }  
     }  
     return dummy.next;  
   }  
 }  

解法二：
divide and conqure
用merge sort的思想，把sort list看成sort number。不断divide，到达递归的终点变成一个merge two sorted list问题。递归的终点是start == end, 返回当前listnode。这个方法居然one pass, 第一次。
代码如下：

 /**  
  * Definition for ListNode.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int val) {  
  *     this.val = val;  
  *     this.next = null;  
  *   }  
  * }  
  */   
 public class Solution {  
   /**  
    * @param lists: a list of ListNode     
    * @return: The head of one sorted list.  
    */  
   public ListNode mergeKLists(List<ListNode> lists) {   
     // write your code here  
     if(lists.size() == 0 || lists == null )  
     {  
       return null;  
     }  
     return mergeSort(0, lists.size() - 1, lists);  
   }  
   private ListNode mergeSort(int start, int end, List<ListNode> lists) {  
     if(start == end) {  
       return lists.get(start);  
     }  
     int mid = start + (end - start) / 2;  
     ListNode a = mergeSort(start, mid, lists);  
     ListNode b = mergeSort(mid + 1, end, lists);  
     return merge(a, b);  
   }  
   private ListNode merge(ListNode a, ListNode b) {  
     ListNode dummy = new ListNode(0);  
     ListNode head = dummy;  
     while(a != null && b != null) {  
       if(a.val < b.val) {  
         head.next = a;  
         head = a;  
         a = a.next;  
       } else {  
         head.next = b;  
         head = b;  
         b = b.next;  
       }  
     }   
     while(a != null) {  
       head.next = a;  
         head = a;  
         a = a.next;  
     }  
     while(b != null) {  
       head.next = b;  
         head = b;  
         b = b.next;  
     }  
     return dummy.next;  
   }  
 }