class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;
        ListNode sentry = new ListNode(0);
        sentry.next = head;
        ListNode sorted = head;
        ListNode cur = sorted.next;
        while (cur != null) {
            if (sorted.val <= cur.val) {
                sorted = sorted.next;
                cur = cur.next;
            } else {
                // 找待插入的位置，小插入第一个比 cur 大的元素的前面
                ListNode insertPrev = sentry;
                while (insertPrev.next.val <= cur.val) {
                    insertPrev = insertPrev.next;
                }
                sorted.next = cur.next; // cur 与 sorted 断开
                cur.next = insertPrev.next; // cur 的 next 接好
                insertPrev.next = cur; // cur 的前一个结点接上 cur
                cur = sorted.next; // cur 指向未排序区域的头部
            }
        }
        return sentry.next;
    }
}