Insertion Sort List

Sort a linked list using insertion sort.
This is insertion sort

Algorithm: 

-1-Create a new head has the same value with the value of original list.
-2-Create two pointers: pointer initialized to point to the second node in the original list, and and innerPointer used to do insertion operation in the new sorted list. InnerPointer is initialized to point to the new head;
-3-There are three parts need you to take care of: update head of the new list; effectively insert node into the new list; update tail the new list.
Note:small bug on dealing with the new head every. Consider if the value of the node waiting to insert has the same value with new head!

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     if (head == null || head.next == null)  
       return head;  
     ListNode newHead = new ListNode(head.val);  
     ListNode pointer = head.next;  
     while(pointer!=null){  
       ListNode innerPointer=newHead;  
       ListNode next=pointer.next;  
       if(newHead.val>=pointer.val){  // "=" is a source of bug!
         ListNode oldHead=newHead;  
         newHead=pointer;  
         newHead.next=oldHead;  
       }else{  
         while(innerPointer.next!=null){  
           if(innerPointer.val<pointer.val&&innerPointer.next.val>=pointer.val){  
             pointer.next=innerPointer.next;  
             innerPointer.next=pointer;  
             break;  
           }  
           innerPointer=innerPointer.next;  
         }  
         if(innerPointer.next==null){  
           innerPointer.next=pointer;  
           pointer.next=null;  
         }  
       }  
       pointer=next;  
     }  
     return newHead;  
   }  
 }