// Definition for singly-linked list.// type ListNode struct {// Val int// Next *ListNode// }funcinsertionSortList(head*ListNode)*ListNode{dummy:ListNode{}// 啞結(jié)點(diǎn)dummy.Next 是已排序部分cur:headforcur!nil{// 保存下一個(gè)待處理節(jié)點(diǎn)next:cur.Next// 在已排序部分找插入位置最后一個(gè) Val cur.Val 的節(jié)點(diǎn)prev:dummyforprev.Next!nilprev.Next.Valcur.Val{prevprev.Next}// 把 cur 插入到 prev 之后cur.Nextprev.Next prev.Nextcur curnext}returndummy.Next}思路和其他語(yǔ)言版本完全一致維護(hù)一個(gè)有序部分每次從原鏈表取出一個(gè)節(jié)點(diǎn)插到有序部分的正確位置。· dummy 是啞結(jié)點(diǎn)dummy.Next 指向已排序鏈表的頭部統(tǒng)一處理「插入到頭部」和「插入到中間」。· 對(duì)每個(gè) cur從 dummy 往后找停在最后一個(gè) Val cur.Val 的節(jié)點(diǎn) prev?！?把 cur 接到 prev 后面?！?先保存 next : cur.Next因?yàn)楹竺鏁?huì)改寫 cur.Next。用 保證穩(wěn)定性相等元素保持原有相對(duì)順序。復(fù)雜度· 時(shí)間O(n2)最壞情況每個(gè)節(jié)點(diǎn)都要從頭掃描已排序部分?！?空間O(1)原地排序只用常數(shù)個(gè)指針。測(cè)試packagemainimportfmttypeListNodestruct{ValintNext*ListNode}funcfromSlice(vals[]int)*ListNode{dummy:ListNode{}cur:dummyfor_,v:rangevals{cur.NextListNode{Val:v}curcur.Next}returndummy.Next}functoSlice(head*ListNode)[]int{varres[]intforhead!nil{resappend(res,head.Val)headhead.Next}returnres}funcmain(){fmt.Println(toSlice(insertionSortList(fromSlice([]int{4,2,1,3}))))// [1 2 3 4]fmt.Println(toSlice(insertionSortList(fromSlice([]int{-1,5,3,4,0}))))// [-1 0 3 4 5]fmt.Println(toSlice(insertionSortList(fromSlice([]int{1}))))// [1]fmt.Println(toSlice(insertionSortList(nil)))// []}小細(xì)節(jié)· Go 里沒(méi)有類方法約束直接寫函數(shù)即可LeetCode 上就是頂層函數(shù)。· dummy : ListNode{} 的 Val 用零值 0 即可比較從 dummy.Next 開(kāi)始?！?如果面試要求寫成方法可以定義 type LRU… 類似的結(jié)構(gòu)但這題通常就寫頂層函數(shù)?！?鏈表節(jié)點(diǎn)是引用語(yǔ)義插入操作只需改 Next 指針天然原地排序。