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

image

插入排序的動畫演示如上。從第一個元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。
每次迭代時，從輸入數(shù)據(jù)中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中。

插入排序算法：

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

示例 1：

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

示例 2：

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
        // 每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?，并將其插入?        // 每次迭代完成，從插入元素為止，該鏈表可以被認(rèn)為已經(jīng)部分排序
        // 重復(fù)直到所有輸入數(shù)據(jù)插入完為止
        
         // 1.遍歷并與前面已經(jīng)有序的序列向前逐一比較排序，找到合適為止插入
        
        // 定義三個指針 pre, cur, lat
        //pre    cur    lat
        // h  ->  4  ->  2  ->  5  ->  3  ->  null
        
        // 創(chuàng)建 h 節(jié)點，用于遍歷鏈表
        ListNode h = new ListNode(-1);
        h.next = head;
        ListNode pre = h;
        ListNode cur = head;
        ListNode lat;
        
        while (cur != null) {
            lat = cur.next; // 記錄下一個要插入排序的值
            
            if (lat != null && lat.val < cur.val) { // 只有 cur.next 比 cur 小才需要向前尋找插入點
                // 尋找插入點，從 pre 開始遍歷 （每次都是頭節(jié)點 h 開始向后遍歷，因為單向鏈表是無法從后往前遍）
                while (pre.next != null && pre.next.val < lat.val) { // 如果當(dāng)前節(jié)點的值小于要插入排序的值
                    pre = pre.next; // 繼續(xù)向后移動
                }
                
                // 找到要插入的位置，此時 pre 節(jié)點后面的位置就是 lat 要插入的位置
                // 交換 pre 跟 lat 節(jié)點需要一個 temp 節(jié)點來臨時保存下插入位置 node 后 next
                ListNode tmp = pre.next;
                // 在 pre 節(jié)點后面插入
                pre.next = lat;
                // 此時 cur 節(jié)點還是 pre 所在的節(jié)點，所以其 next 要指向插入節(jié)點 lat 指向的 next
                cur.next = lat.next;
                // 插入let節(jié)點后，把記錄的原先插入位置后續(xù)的 next 節(jié)點傳給它
                lat.next = tmp;
                // 由于每次都是從前往后找插入位置，但是單向鏈表是無法從后往前遍歷，所以需要每次插入完成后要讓 pre 復(fù)位
                pre = h;
            } else {
                // 都這直接把 cur 指針指向到下一個
                cur = lat;
            }
        }
        
       return h.next;
    }
}