// Definition for singly-linked list.// type ListNode struct {// Val int// Next *ListNode// }funcinsertionSortList(head*ListNode)*ListNode{dummy:ListNode{}// 啞結點dummy.Next 是已排序部分cur:headforcur!nil{// 保存下一個待處理節(jié)點next:cur.Next// 在已排序部分找插入位置最后一個 Val cur.Val 的節(jié)點prev:dummyforprev.Next!nilprev.Next.Valcur.Val{prevprev.Next}// 把 cur 插入到 prev 之后cur.Nextprev.Next prev.Nextcur curnext}returndummy.Next}思路和其他語言版本完全一致維護一個有序部分每次從原鏈表取出一個節(jié)點插到有序部分的正確位置?！?dummy 是啞結點dummy.Next 指向已排序鏈表的頭部統(tǒng)一處理「插入到頭部」和「插入到中間」?！?對每個 cur從 dummy 往后找停在最后一個 Val cur.Val 的節(jié)點 prev?！?把 cur 接到 prev 后面?！?先保存 next : cur.Next因為后面會改寫 cur.Next。用 保證穩(wěn)定性相等元素保持原有相對順序。復雜度· 時間O(n2)最壞情況每個節(jié)點都要從頭掃描已排序部分?！?空間O(1)原地排序只用常數個指針。測試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)))// []}小細節(jié)· Go 里沒有類方法約束直接寫函數即可LeetCode 上就是頂層函數?！?dummy : ListNode{} 的 Val 用零值 0 即可比較從 dummy.Next 開始?！?如果面試要求寫成方法可以定義 type LRU… 類似的結構但這題通常就寫頂層函數。· 鏈表節(jié)點是引用語義插入操作只需改 Next 指針天然原地排序。