class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null)
            return head;
        ListNode dummy = new ListNode(java.lang.Integer.MIN_VALUE);
        dummy.next = head;
        ListNode last = dummy.next; //需要插入的节点的上一个节点
        ListNode cur = last.next;   //当前需要插入的节点
        while(cur != null){
            ListNode pre = dummy;  //插入处的前一节点
            ListNode post = pre.next;  //插入处的后一节点
            while(post != cur){
                if(cur.val >= pre.val && cur.val < post.val){
                    last.next = cur.next;
                    cur.next = post;
                    pre.next = cur;
                    break;
                }else{
                    pre = post;
                    post = pre.next;
                }
            }
            last = cur;
            cur = last.next;
        }
        return dummy.next;
    }
}