企业官网建设流程全解析

// Definition for singly-linked list.// type ListNode struct {// Val int// Next *ListNode// }funcinsertionSortList(head*ListNode)*ListNode{dummy:=&ListNode{}// 哑结点，dummy.Next 是已排序部分cur:=headforcur!=nil{// 保存下一个待处理节点next:=cur.Next// 在已排序部分找插入位置：最后一个 Val <= cur.Val 的节点prev:=dummyforprev.Next!=nil&&prev.Next.Val<=cur.Val{prev=prev.Next}// 把 cur 插入到 prev 之后cur.Next=prev.Next prev.Next=cur cur=next}returndummy.Next}

思路

和其他语言版本完全一致：维护一个有序部分，每次从原链表取出一个节点，插到有序部分的正确位置。

· dummy 是哑结点，dummy.Next 指向已排序链表的头部，统一处理「插入到头部」和「插入到中间」。
· 对每个 cur，从 dummy 往后找，停在最后一个 Val <= cur.Val 的节点 prev。
· 把 cur 接到 prev 后面。
· 先保存 next := cur.Next，因为后面会改写 cur.Next。

用 <= 保证稳定性：相等元素保持原有相对顺序。

复杂度

· 时间：O(n²)，最坏情况每个节点都要从头扫描已排序部分。
· 空间：O(1)，原地排序，只用常数个指针。

测试

packagemainimport"fmt"typeListNodestruct{ValintNext*ListNode}funcfromSlice(vals[]int)*ListNode{dummy:=&ListNode{}cur:=dummyfor_,v:=rangevals{cur.Next=&ListNode{Val:v}cur=cur.Next}returndummy.Next}functoSlice(head*ListNode)[]int{varres[]intforhead!=nil{res=append(res,head.Val)head=head.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)))// []}

小细节

· Go 里没有类方法约束，直接写函数即可（LeetCode 上就是顶层函数）。
· dummy := &ListNode{} 的 Val 用零值 0 即可，比较从 dummy.Next 开始。
· 如果面试要求写成方法，可以定义 type LRU… 类似的结构，但这题通常就写顶层函数。
· 链表节点是引用语义，插入操作只需改 Next 指针，天然原地排序。