public ListNode insertionSortList(ListNode head) {
        if(head == null) return head;
        ListNode cur = head.next, pre = head, p, q, next, nextPre = null;
        
        while(cur != null) {
            next = cur.next;
            p = null;
            q = head;
            while(cur.val > q.val) {
                p = q;
                q = q.next;
            }
            if(p == null) {
                pre.next = cur.next;
                cur.next = head;
                head = cur;
                nextPre = pre;
            } else if(cur != q) {
                pre.next = cur.next;
                cur.next = p.next;
                p.next = cur;
                nextPre = pre;
            } else {
                nextPre = cur;
            }
            pre = nextPre;
            cur = next;
        }
        return head;
    }