文章

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode res = new ListNode(0, head);
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (pre.val <= cur.val) {
                pre = pre.next;
            } else {
                ListNode temp = res;
                while (cur.val >= temp.next.val) {
                    temp = temp.next;
                }
                pre.next = cur.next;
                cur.next = temp.next;
                temp.next = cur;
            }
            cur = pre.next;
        }
        return res.next;
    }
}