LeetCode 147.Insertion Sort List (對連結清單進行插入排序)

題目描述：

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

插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。

每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。

插入排序算法：

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

示例 1：

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

示例 2：

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

AC C++ Solution:

解題思路：

保留一個已排序的部分清單（head）并從第二個節點（head -> next）開始，每次當我們看到一個val比前一個節點小的節點時，我們從中掃描head并找到該節點應該插入的位置。因為可能插入節點到head之前，是以我們建立了dummy指向的頭部head。

C++ code:

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;
        
        while(cur) {
            if((cur->next) && (cur->next->val < cur->val)) {                //每當後一個節點的值比前一個節點小時
                while((pre->next) && (pre->next->val < cur->next->val)) {   //尋找插入位置
                    pre = pre->next;
                }
                
                ListNode* temp = pre->next;         //将節點插入到前面已排序清單中
                pre->next = cur->next;
                cur->next = cur->next->next;
                pre->next->next = temp;
                pre = dummy;
            }
            else {
                cur = cur->next;
            }
        }
        
        return dummy->next;
    }
};