LeetCode-Go 题解：147. Insertion Sort List 链表的插入排序实现与源码解析

LeetCode-Go 题解147. Insertion Sort List 链表的插入排序实现与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 第 147 题「Insertion Sort List链表的插入排序」为核心完整讲解插入排序算法在单链表上的实现思路并结合 LeetCode-Go 仓库中该题的官方 Go 解法源码leetcode/0147.Insertion-Sort-List/147. Insertion Sort List.go逐行剖析其哨兵节点、内层查找与节点摘插的细节。读完本文你将掌握如何在 O(n²) 时间复杂度、O(1) 额外空间下对链表完成原地插入排序并了解仓库配套的测试用例与链表工具函数的使用方式。题目回顾题目要求使用插入排序算法对一个单链表进行排序Sort a linked list using insertion sort。插入排序算法定义插入排序是每次迭代消费一个输入元素并逐渐生长出一个已排序输出链表的排序方式。具体过程为每次迭代从输入数据中移除一个元素在已排序链表中找到该元素应该归属的位置将它插入到该位置重复以上步骤直到输入数据中不再有剩余元素。插入排序的图形化示例中黑色部分表示初始只包含链表第一个元素的已排序部分每次迭代从输入数据中取出一个元素红色并把它就地插入到已排序列表中。示例示例 1Input: 4-2-1-3 Output: 1-2-3-4示例 2Input: -1-5-3-4-0 Output: -1-0-3-4-5核心思路链表上的就地插入排序数组上的插入排序依赖下标随机访问来搬移元素而单链表只能顺序遍历因此链表版本的关键在于「节点指针的摘除与重连」而非值交换。整体策略是维护一个已排序链表初始为空或只含哨兵依次从原始链表中摘下当前节点cur在已排序链表中从前往后找到第一个值大于等于cur.Val的节点位置将cur插入到其前面重复直到原链表为空。时间复杂度为 O(n²)最坏情况额外空间为 O(1)完全符合题目对原地排序的要求。Go 源码逐行解析仓库中该题的完整实现如下leetcode/0147.Insertion-Sort-List/147. Insertion Sort List.gopackage leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func insertionSortList(head *ListNode) *ListNode { if head nil { return head } newHead : ListNode{Val: 0, Next: nil} // 这里初始化不要直接指向 head为了下面循环可以统一处理 cur, pre : head, newHead for cur ! nil { next : cur.Next for pre.Next ! nil pre.Next.Val cur.Val { pre pre.Next } cur.Next pre.Next pre.Next cur pre newHead // 归位重头开始 cur next } return newHead.Next }下面按关键点逐段拆解。1. 链表节点类型的统一type ListNode structures.ListNode源码通过类型别名type ListNode structures.ListNode复用了仓库统一封装的链表结构其定义位于 structures/ListNode.go// ListNode 是链接节点 type ListNode struct { Val int Next *ListNode }这意味着所有链表题解共享同一套节点定义与工具函数便于测试用例的构造与断言。2. 哨兵节点让循环统一处理newHead : ListNode{Val: 0, Next: nil}代码注释明确指出初始化时不要直接指向 head而是引入一个值为 0 的哨兵节点dummy node。这样做的好处是插入位置可能是已排序链表的头部即所有已排序元素都大于当前节点哨兵节点让头插与中间插入的逻辑完全一致无需特判最终返回值newHead.Next即排序后的链表头。3. 外循环逐个摘下原链表的节点cur, pre : head, newHead for cur ! nil { next : cur.Next // 先记录后继防止断链 ... pre newHead // 每次插入后 pre 归位到哨兵从头开始找位置 cur next }外循环遍历原链表cur是当前待插入节点。由于随后要修改cur.Next必须先保存next每完成一次插入pre重新指向哨兵节点保证内层查找总是从已排序链表头部开始。4. 内循环在已排序链表中定位插入点for pre.Next ! nil pre.Next.Val cur.Val { pre pre.Next }内循环从pre哨兵出发只要pre.Next存在且其值小于cur.Val就继续后移。循环退出时pre恰好停在「值小于cur.Val的最后一个节点」上因此cur应插入到pre与pre.Next之间。该查找过程维持了插入排序的稳定性——遇到相等值时不会越过相等元素的相对顺序得以保留。5. 摘插指针重连完成原地插入cur.Next pre.Next pre.Next cur两步完成插入先把cur接到pre.Next之后再把pre.Next指向cur。由于cur已被摘除这段操作不依赖额外数组或缓存额外空间保持 O(1)。6. 边界情况处理空链表head nil函数直接返回head即nil单节点链表外循环仅执行一次内循环因pre.Next.Val cur.Val不成立或已到尾部而立即退出节点被插到哨兵之后结果正确全部逆序/正序输入分别对应最坏 O(n²) 与最好 O(n) 的查找开销代码路径无需任何特判。复杂度分析指标数值说明时间复杂度O(n²)内层查找每次最多遍历已排序部分最坏为 12...n最好情况O(n)输入已有序时每个节点的查找都只需一次比较空间复杂度O(1)仅使用哨兵节点与若干指针变量测试用例与验证方式仓库为本题提供了配套测试leetcode/0147.Insertion-Sort-List/147. Insertion Sort List_test.go覆盖了题目给出的两个示例以及单节点、空链表等边界场景输入期望输出覆盖场景[4, 2, 1, 3][1, 2, 3, 4]示例 1普通乱序[1][1]单节点边界[-1, 5, 3, 4, 0][-1, 0, 3, 4, 5]示例 2含负数与部分有序[][]空链表边界测试中通过structures.Ints2List将整数切片转换为链表再调用insertionSortList最后用structures.List2Ints转回切片断言结果。这两个工具函数同样定义在 structures/ListNode.go 中Ints2ListL37-L49负责构造链表List2IntsL15-L34负责将链表还原为切片并带有 100 层深度限制用于防范环状链表导致的死循环。若在仓库根目录使用go test ./leetcode/0147.Insertion-Sort-List/...即可运行本题测试运行前提是本机已安装 Go 工具链并完成模块依赖拉取。扩展与其他链表排序方案的对比理解插入排序在链表上的实现后可以将其与同仓库中的其他链表排序题解做横向比较以加深对排序算法适用场景的认识插入排序本题实现简单、稳定、对「近似有序」的链表表现良好最坏 O(n²)归并排序链表天然适合归并无需随机访问可将复杂度稳定降为 O(n log n)是处理大规模链表排序的首选对应仓库中 0148.Sort-List 等题解快速排序在链表上需要额外的指针维护与分区逻辑实际工程中较少直接用于链表。实际编码中若链表规模较小或基本有序本题解法足够高效若追求稳定的大 O 复杂度则应改用链表归并排序。小结LeetCode 147 的链表插入排序是理解「指针摘插」与「哨兵节点」技巧的经典题目。本文以 LeetCode-Go 仓库的官方实现为蓝本梳理了哨兵节点统一边界、外循环摘节点、内循环定位、两步指针重连插入的完整链路并结合仓库测试用例与链表工具函数说明了验证方法。掌握这一实现后你可以直接阅读 leetcode/0147.Insertion-Sort-List/README.md 回顾题目要点或在 leetcode/0148.Sort-List 中进一步学习链表 O(n log n) 排序的进阶方案。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考