147. 對鏈表進(jìn)行插入排序

插入排序算法：
插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?，并將其插入?br> 重復(fù)直到所有輸入數(shù)據(jù)插入完為止。
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

思路

1 cur節(jié)點(diǎn)為要插入到有序鏈表的節(jié)點(diǎn)
2 首先將cur與有序鏈表中的尾結(jié)點(diǎn)比較，如果已排序尾結(jié)點(diǎn)小于等于要插入的節(jié)點(diǎn)，則要插入的節(jié)點(diǎn)已經(jīng)在正確的位置，無需挪動。將尾結(jié)點(diǎn)向后移一個即可
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;
            //先比較要插入的節(jié)點(diǎn)和已排序的鏈表中尾結(jié)點(diǎn)。
            // 如果已排序尾結(jié)點(diǎn)小于等于要插入的節(jié)點(diǎn)，則要插入的節(jié)點(diǎn)已經(jīng)在正確的位置，無需挪動。
            // 將尾結(jié)點(diǎn)向后移一個即可
            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;
    }

}