主題
題目連結：
題目意譯：
給定一個單向鏈結串列（Singly Linked List）的開頭 head，使用插入排序（Insertion Sort）來將此串列排序好，並回傳這個排序後的串列之開頭。
插入排序演算法的步驟為下：
插入排序採取迭代之方式，每次消耗掉輸入中的一個元素並使已排序部分之串列大小增加。
每一次迭代中，插入排序從輸入中移出一個元素，找出其在已排序之部分所屬位置並將其插入該位置。
其將重複直到沒有輸入元素剩下為止。
下圖為一個插入排序演算法之動畫範例。這個部分排序之串列（黑色框起之部分）一開始只包含串列中的第一個元素。每一次迭代中，一個元素（以紅色框起）被從輸入中移出並「原地」（In-place）地插入到已排序串列中。
限制：
串列中的節點數位於範圍 [1, 5000]。
-5000 ≦ Node.val ≦ 5000
範例測資：
範例 1：
輸入： head = [4,2,1,3]
輸出： [1,2,3,4]
範例 2：
輸入： head = [-1,5,3,4,0]
輸出： [-1,0,3,4,5]
解題思維：
首先我們建立一個暫時性的節點 dummy 作為已排序串列的開頭。而為了方便，可以將 dummy 的節點值設為足夠小的數值（例如 -5001）。
為什麼需要這個 dummy 呢？因為如果直接拿串列第一個作為開頭，有可能後面會遇到需要插在這個開頭前面作為新開頭的節點，而這樣實際上不太好寫。有了 dummy 這個假的頭就會好上很多。因為根據我們的設定節點值，它不會到處移動（不會有節點跑到 dummy 前面）。
接著我們就每次從原本的串列依序拿一個節點 X 過來到這個已排序之串列中作比較，作法很簡單：
用一個指標 current 從 dummy->next 開始以及另一個指標 last 作為 current 的「前一個」節點（last 一開始為 dummy）。
接著就掃過已排序串列，直到遇到 current 指到的節點之值大於 X 之值或是 current 為空指標。此時我們可以看到節點 X 應插入於 last 和 current 之間，因此令
last->next 指向 X；
X->next 指向 current。
整個掃完之後即可完成鏈結串列的插入排序法。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
