[数据结构与算法]147. 对链表进行插入排序

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode lastSorted = head, current = head.next;
        while (current != null) {
            //current先和维护好顺序序列的最后一个值比较，如果比他大就直接右移了
            if (lastSorted.val < current.val) {
                lastSorted = lastSorted.next;
            } else {
                //否则就要从头开始比较找到插入的位置，每次都把prev置于最开始
                ListNode prev = dummy;
                //如果current大于移动指针prev的话，prev就继续向后移
                while (current.val > prev.next.val) {
                    prev = prev.next;
                }
                //出了循环，prev.next比current大了，开始插入
                lastSorted.next = current.next;
                current.next = prev.next;
                prev.next = current;
            }
            //current置换到已经排好顺序序列的后面一个
            current = lastSorted.next;
        }
        return dummy.next;
    }
}

来源：LeetCode官方