Sort a linked list using insertion sort.

s思路： 1. insertion sort這個思路是這樣的：遍歷從第二個數(shù)據(jù)開始，第一個數(shù)據(jù)默認是排好序的，把第二個數(shù)據(jù)和第一個數(shù)比較插入，從而sorted的序列expanded by one, while the unsorted sequence is shrinked by one as well. 復(fù)雜度o(n^2). 2. 通常的insertion sort都是默認在vector上執(zhí)行，這道題新穎的地方就是在鏈表上來做。也就是，當鏈表遇到insertion sort，會有什么事情發(fā)生？ 3. 其實可以見怪不怪的，這兩個對象（鏈表和insertion sort）一旦被人們發(fā)現(xiàn)，他們之間的關(guān)系就已經(jīng)當即存在，只是現(xiàn)在我才看到而已，本身不是什么新鮮事！ 4. 參考了以前代碼，添加dummy好做一些，自己用pointer-to-pointer搞不定，搞暈了：cur代表sorted的最右邊，每次用cur和cur->next比較，如果cur->val > cur->next->val,則此時就是邊界，然后讓PRe從dummy開始往后移動找到pre->next->val > cur->next->val,然后把cur->next這個節(jié)點插入到pre和pre->next之間。 5. 自己做的時候，嘗試中規(guī)中矩的做:每次把sorted的右邊界的next節(jié)點和之前的所有節(jié)點比較，找到合適的位置，然后插入。由于頭節(jié)點可能改變，因此也用dummy節(jié)點；在比較的時候，也知道要找的插入的位置必須是某個指針的next，而不是某個指針之前的位置（因為鏈表只有next域沒有pre域）。這樣做的問題是，不能充分利用鏈表中可能存在的排好序的子鏈表，例如:3->2->4->1,當前兩個排好序時：2->3->4->1,2和3 就不需要排序，因為是以及排好序的，所以可以節(jié)省時間！ 6. 整理一下思路：這種思路好在，每次從unsorted部分取第一個數(shù)都和sorted的最后一個數(shù)比較：如果大，則直接移動sorted的邊界；如果小，才比較去找這個數(shù)應(yīng)該在sorted部分的正確位置。 7. 自己為啥沒想到呢？仔細觀察自己的思路：默認一個新的數(shù)，直接就和sorted的部分從左往右比較了；先和右邊界比較可以省事很多這點沒有意識到！