Note:

每次都需要从开头看，判断cur该插在哪里

如何移动prev指针：

while (prev.next != null && prev.next.val <= cur.val)

prev = prev.next;

Key word:

class Solution {
    public ListNode insertionSortList(ListNode head) {
       ListNode dummy = new ListNode();
       ListNode cur = head;

       while (cur != null) {
           ListNode prev = dummy;
           while (prev.next != null && prev.next.val <= cur.val) {
               prev = prev.next;
           }
           ListNode next = cur.next;
           cur.next = prev.next;
           prev.next = cur;
           cur = next;
       } 
       return dummy.next;
    }
}

Complexity Analysis:

TC: O(n^2);

SC: O(1);