147. Insertion Sort List

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode insertionSortList(ListNode head) {
11         if(head==null) return head;//corner case:if the List is null;
12         ListNode helper = new ListNode(0);
13         ListNode pre = helper,//insert between pre and pre.next
14         cur = head,//the node will be inserted
15         next = null;//the next node will be valued by cur
16         while(cur!=null){
17             next = cur.next;
18             // find the right place to insert
19             while(pre.next!=null&&pre.next.val<cur.val){
20                 pre=  pre.next;
21             }
22             // insert between pre and pre.next
23             cur.next = pre.next;
24             pre.next = cur;
25             pre = helper;
26             cur = next;
27         }
28         return helper.next;
29     }
30 }
31 // as for the run time complexity,for the worst case, it will cost O(n^2) time. As for the space complexity,it will take O(n)