147. 对链表进行插入排序

插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路

1 cur节点为要插入到有序链表的节点
2 首先将cur与有序链表中的尾结点比较，如果已排序尾结点小于等于要插入的节点，则要插入的节点已经在正确的位置，无需挪动。将尾结点向后移一个即可
3 否则，从头遍历有序链表，找到cur的位置，将其插入即可

代码

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode sentinal = new ListNode(Integer.MIN_VALUE);
        sentinal.next = head;
        ListNode cur = head.next;
        ListNode p1;
        ListNode p2;
        ListNode newTail = head;
        while (cur != null){
            p1 = sentinal;
            p2 = sentinal.next;
            //先比较要插入的节点和已排序的链表中尾结点。
            // 如果已排序尾结点小于等于要插入的节点，则要插入的节点已经在正确的位置，无需挪动。
            // 将尾结点向后移一个即可
            if (newTail.val <= cur.val){
                newTail = cur;
                cur = cur.next;
                continue;
            }
            while (cur.val >= p2.val){
                p1 = p1.next;
                p2 = p2.next;
            }
            newTail.next = cur.next;
            cur.next = p2;
            p1.next = cur;
            cur = newTail.next;

        }
        return sentinal.next;
    }

}