Leetcode-Merge k Sorted Lists

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeKLists(List<ListNode> lists) {
14         //Consider the cases where the element in lists is NULL!
15         for (int i=0;i<lists.size();i++)
16             if (lists.get(i)==null){
17                 lists.remove(i);
18                 i--;
19             }
20         if (lists.size()==0) return null;
21         if (lists.size()==1) return lists.get(0);
22 
23         ListNode preHead = new ListNode(0);
24         ListNode end = preHead;
25         List<ListNode> curList = new ArrayList<ListNode>();
26         curList.add(lists.get(0));
27         for (int i=1;i<lists.size();i++) binaryInsert(curList,lists.get(i));
28         while (curList.size()!=0){
29             if (curList.size()==1){
30                 end.next = curList.get(0);
31                 end = new ListNode(0);
32                 break;
33             }
34             ListNode target = curList.get(0);            
35             curList.remove(0);
36             if (target.next!=null) binaryInsert(curList,target.next);
37             end.next = target;
38             end = target;
39         }
40         end.next = null;
41         return preHead.next;
42         
43     }
44 
45     public void binaryInsert(List<ListNode> lists, ListNode node){
46         int start = 0;
47         int end = lists.size()-1;
48         int index = -1;
49         while (start<end){
50             int mid = (start+end)/2;
51             if (node.val == lists.get(mid).val){
52                 index = mid;
53                 break;
54             }
55 
56             if (node.val>lists.get(mid).val){
57                 start = mid+1;
58                 continue;
59             }
60 
61             if (node.val<lists.get(mid).val){
62                 end = mid-1;
63                 continue;
64             }
65         }
66         
67         //NOTE: There are two ending cases, we need consider them carefully!.
68         if (index==-1){
69             if (start==end)
70                 if (node.val>lists.get(start).val) index=start+1;
71                 else index = start;
72             else index = start;   //i.e., start>end.
73         }  
74 
75         lists.add(index,node);
76 
77         return;
78     }        
79 }