// 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!nilprev.Next.Valcur.Val{prevprev.Next}// 把 cur 插入到 prev 之后cur.Nextprev.Next prev.Nextcur curnext}returndummy.Next}思路和其他语言版本完全一致维护一个有序部分每次从原链表取出一个节点插到有序部分的正确位置。· dummy 是哑结点dummy.Next 指向已排序链表的头部统一处理「插入到头部」和「插入到中间」。· 对每个 cur从 dummy 往后找停在最后一个 Val cur.Val 的节点 prev。· 把 cur 接到 prev 后面。· 先保存 next : cur.Next因为后面会改写 cur.Next。用 保证稳定性相等元素保持原有相对顺序。复杂度· 时间O(n²)最坏情况每个节点都要从头扫描已排序部分。· 空间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)))// []}小细节· Go 里没有类方法约束直接写函数即可LeetCode 上就是顶层函数。· dummy : ListNode{} 的 Val 用零值 0 即可比较从 dummy.Next 开始。· 如果面试要求写成方法可以定义 type LRU… 类似的结构但这题通常就写顶层函数。· 链表节点是引用语义插入操作只需改 Next 指针天然原地排序。 DeepSeek LeetCode 147. 对链表进行插入排序 Golang实现
// 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!nilprev.Next.Valcur.Val{prevprev.Next}// 把 cur 插入到 prev 之后cur.Nextprev.Next prev.Nextcur curnext}returndummy.Next}思路和其他语言版本完全一致维护一个有序部分每次从原链表取出一个节点插到有序部分的正确位置。· dummy 是哑结点dummy.Next 指向已排序链表的头部统一处理「插入到头部」和「插入到中间」。· 对每个 cur从 dummy 往后找停在最后一个 Val cur.Val 的节点 prev。· 把 cur 接到 prev 后面。· 先保存 next : cur.Next因为后面会改写 cur.Next。用 保证稳定性相等元素保持原有相对顺序。复杂度· 时间O(n²)最坏情况每个节点都要从头扫描已排序部分。· 空间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)))// []}小细节· Go 里没有类方法约束直接写函数即可LeetCode 上就是顶层函数。· dummy : ListNode{} 的 Val 用零值 0 即可比较从 dummy.Next 开始。· 如果面试要求写成方法可以定义 type LRU… 类似的结构但这题通常就写顶层函数。· 链表节点是引用语义插入操作只需改 Next 指针天然原地排序。