147. Insertion Sort List #

题目 #

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

思路 #

代码 #

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode insertSortList(ListNode head) {
        ListNode sentinel = new ListNode(-1, head);
        
        /** 设置 preserve 指向已排序链表的尾结点，每次新处理的结点为 preserve.next */
        ListNode preserve = sentinel, toInsert = preserve.next;
        while (toInsert != null) {
            ListNode ptr = sentinel;
            while (ptr != preserve && ptr.next.val <= toInsert.val) ptr = ptr.next;
            if (ptr == preserve) {
                preserve = preserve.next;
                toInsert = preserve.next;
            } else {
                preserve.next = toInsert.next;
                toInsert.next = ptr.next;
                ptr.next = toInsert;
                toInsert = preserve.next;
            }
        }
        return sentinel.next;
    }
}