每日LeetCode 217

217

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

3. 重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

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;
    }
}