leetcode -- Insertion Sort List

 1 public ListNode insertionSortList(ListNode head) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         if(head == null){
 5             return head;
 6         }
 7         ListNode dummyHead = new ListNode(-2147483648);
 8         ListNode p1 = dummyHead, p2 = head;
 9         
10         while(p2 != null){
11             ListNode pre = findInsertPlace(p1, p2);
12             // insert into list
13             // save orignal list next node
14             ListNode originalNext = p2.next;
15             p2.next = pre.next;
16             pre.next = p2;
17             
18             p2 = originalNext;
19         }
20         
21         return dummyHead.next;
22     }
23     
24     public ListNode findInsertPlace(ListNode p1, ListNode p2){
25         ListNode pre = null, cur = p1;
26         while(cur != null && cur.val <= p2.val){
27             pre = cur;
28             cur = cur.next;
29         }
30         return pre;
31     }