對連結清單進行插入排序（從前往後周遊簡單實作）

題目

對連結清單進行插入排序。

• 插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。
• 每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。

插入排序算法：

• 插入排序是疊代的，每次隻移動一個元素，直到所有元素可以形成一個有序的輸出清單。
• 每次疊代中，插入排序隻從輸入資料中移除一個待排序的元素，找到它在序列中适當的位置，并将其插入。
• 重複直到所有輸入資料插入完為止。

示例 ：

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

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

注意點

無序時插入操作大概如下：

實作

/**
 * 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) {
            return null;
        }

		// 啞節點dummp用于記錄連結清單頭節點（便于插入節點時的從前往後周遊）
        ListNode dummy = new ListNode(-1);
        // 啞節點下一節點指向連結清單第一個節點（便于插入節點時記錄前一節點）
        dummy.next = head;
        // 有序連結清單的尾指針（避免每次插入節點後都要從頭開始周遊）
        ListNode lastSorted = head;
        // 插入節點（有序連結清單的下一節點）
        ListNode insertNode = lastSorted.next;

		// 循環處理插入節點
        while (insertNode != null) {
        	// 判斷插入節點與有序連結清單組成的連結清單是否有序（這裡是升序——從小到大）
            if (lastSorted.val <= insertNode.val) {
            	// 有序，則有序連結清單尾指針後移
                lastSorted = lastSorted.next;
                // 插入節點指針後移（此處也可寫為insertNode = lastSorted.next，
                // 且可以與無序時合并，這裡為了便于了解，是以沒有進行合并）
                insertNode = insertNode.next;
            } else {
            	// 無序，則擷取有序連結清單頭節點
                ListNode pre = dummy;
                // 尋找插入節點應該插入的位置（pre是比較節點的前驅節點，便于插入節點的處理）
                while (pre.next.val <= insertNode.val) {
                    pre = pre.next;
                }
                // 下面三個操作是将插入節點插入到合适的位置（修改指針）
                lastSorted.next = insertNode.next;
                insertNode.next = pre.next;
                pre.next = insertNode;
                
                // 插入節點後移
                insertNode = lastSorted.next;
            }
        }

        return dummy.next;
    }
}