147. Insertion Sort List

Two Pointers

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, head);
        ListNode orderedTail = head, curr = head.next; // orderedTail 可以从 head 开始，不必从 dummyHead 开始。在整个驱动过程中，orderedTail 与 curr 紧挨并同步移动

        while (curr != null) {
            if (curr.val >= orderedTail.val) {
                orderedTail = curr;
                curr = curr.next;
            } else {
                // 需要将 curr 节点插入到之前已排序的链表中
                ListNode next = curr.next;

                // 将 curr 从链表中摘除
                orderedTail.next = next;

                // 找到插入点进行插入
                ListNode pre = dummyHead;
                while (pre.next.val < curr.val) {
                    pre = pre.next;
                }
                // now: pre.next.val >= curr.val
                curr.next = pre.next;
                pre.next = curr;

                curr = next;
            }
        }

        return dummyHead.next;
    }
}

References

147. Insertion Sort List