Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 

第一遍：

1 public class Solution { 2     public ListNode mergeKLists(ArrayList
     
       lists) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         if(lists.size()==0) return null; 6         ListNode header = new ListNode(-1), cur = header; 7         // boolean sig = true; 8         while(true){ 9             int pos = -1;10             for(int i = 0; i < lists.size(); i ++){11                 if(lists.get(i) != null && (pos == -1 || lists.get(i).val < lists.get(pos).val))12                     pos = i;13             }14             if(pos != -1){15                 cur.next = lists.get(pos);16                 cur = cur.next;17                 lists.set(pos,lists.get(pos).next);18 19             }else{20                 break;21             }22         }23         return header.next;24     }25 }
     

 

第三遍：

去掉 null的项 可以加速 查找。

1 public class Solution { 2     public ListNode mergeKLists(ArrayList
     
       lists) { 3         ListNode header = new ListNode(-1); 4         ListNode cur = header; 5         if(lists == null || lists.size() == 0) return null; 6         while(true){ 7             int min = -1; 8             for(int i = 0; i < lists.size(); i ++){ 9                 if(lists.get(i) == null){10                     lists.remove(i);11                     i --;12                 }13                 else if(min == -1 || lists.get(i).val < lists.get(min).val)14                     min = i;15             }16             if(min == -1) break;17             else{18                 cur.next = lists.get(min);19                 lists.set(min,lists.get(min).next);20                 cur = cur.next;21             }22         }23         return header.next;24     }25 }