Sort a linked list using insertion sort.

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