Insertion Sort List

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         if(head==null) return head;
 4         ListNode safe = new ListNode(Integer.MIN_VALUE);
 5         ListNode p2 = head;
 6         while(p2!=null){
 7             ListNode pre = find(safe,p2);
 8             ListNode next = p2.next;
 9             p2.next = pre.next;
10             pre.next = p2;
11             p2 = next;
12         }
13         return safe.next;
14     }
15     public ListNode find(ListNode p1,ListNode p2){
16         ListNode cur = p1, pre = null;
17         while(cur!=null && cur.val<=p2.val){
18             pre = cur;
19             cur = cur.next;
20         }
21         return pre;
22     }
23 }