LeetCode-Go 链表专题虚拟头结点、递归与归并排序的题解方法论【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode-Go 仓库中 链表专题文档 展开系统梳理单链表类题目最核心的七类解题范式虚拟头结点、递归、区间逆序、快慢指针找中点/倒数第 n 个节点、K 路归并、链表归类、归并排序以及环形链表与相交链表判定。文中将结合仓库leetcode/下对应题目的 Go 实现源码逐一给出可直接复用的代码模板与复杂度结论帮助读者建立一套看到链表题就知道该往哪个方向想的解题框架。一、虚拟头结点统一遍历逻辑的关键技巧链表题最大的痛点在于边界处理当操作可能发生在头结点head身上时删除、反转、分区等逻辑都要单独判断头结点是否为空、是否被修改。虚拟头结点dummy node通过在真实头结点前额外挂一个哨兵节点让所有操作都统一为对中间节点操作从而消解边界分支。核心原则构造虚拟头结点使遍历处理逻辑更加统一。仓库中的 ListNode 定义位于 structures/ListNode.go链表的序列化/反序列化辅助函数List2Ints、Ints2List也在同一文件便于测试时构造用例type ListNode struct { Val int Next *ListNode }应用实例92. Reverse Linked List II区间逆序m 到 n 反转是虚拟头结点的经典使用场景。仓库实现见 leetcode/0092.Reverse-Linked-List-II/92. Reverse Linked List II.gofunc reverseBetween(head *ListNode, m int, n int) *ListNode { if head nil || m n { return head } newHead : ListNode{Val: 0, Next: head} pre : newHead for count : 0; pre.Next ! nil count m-1; count { pre pre.Next } if pre.Next nil { return head } cur : pre.Next for i : 0; i n-m; i { tmp : pre.Next pre.Next cur.Next cur.Next cur.Next.Next pre.Next.Next tmp } return newHead.Next }关键点在于newHead : ListNode{Val: 0, Next: head}即使m 1从头结点开始反转pre依然有前驱反转逻辑无需特判。最终返回newHead.Next即为新链表头。二、递归巧解链表但需警惕栈溢出链表天然具有递归结构Next指针指向子链表因此很多题目可以构造递归条件巧妙求解。仓库中mergeTwoLists就是一个典型递归实现见 leetcode/0148.Sort-List/148. Sort List.gofunc mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 nil { return l2 } if l2 nil { return l1 } if l1.Val l2.Val { l1.Next mergeTwoLists(l1.Next, l2) return l1 } l2.Next mergeTwoLists(l1, l2.Next) return l2 }⚠️ 注意递归深度过深会导致超时和栈溢出。对于超长链表应改用迭代版本或显式栈。这是链表题中递归虽美、但需权衡的重要边界。三、链表区间逆序第 92 题在 第一节 已经给出了 92. Reverse Linked List II 的完整实现。该方法时间复杂度 O(n)、空间复杂度 O(1)采用头插法思路用虚拟头结点定位m-1位置的节点pre固定cur : pre.Next为区间起点循环n-m次每次把cur.Next摘下来插到pre后面逐步完成区间逆序。这也是解决 25. Reverse Nodes in k-Group 的前置技能。四、快慢指针一次遍历找中间节点与倒数第 n 个节点链表无法随机访问但可以用快慢指针在一次遍历内解决问题寻找中间节点慢指针每次走 1 步快指针每次走 2 步快指针到末尾时慢指针恰在中点附近对应第 876 题寻找倒数第 n 个节点让快指针先走 n 步再让快慢指针同步前进快指针到达末尾时慢指针即为倒数第 n 个节点对应第 19 题。876. Middle of the Linked List 仓库实现见 leetcode/0876.Middle-of-the-Linked-List/876. Middle of the Linked List.gofunc middleNode(head *ListNode) *ListNode { if head nil || head.Next nil { return head } p1 : head p2 : head for p2.Next ! nil p2.Next.Next ! nil { p1 p1.Next p2 p2.Next.Next } length : 0 cur : head for cur ! nil { length cur cur.Next } if length%2 0 { return p1.Next } return p1 }注意偶数长度时中点的取法题目要求返回第二个中间节点因此代码先统计链表长度偶数时返回p1.Next。这也是 148. Sort List 归并排序找切分点的核心依赖。五、合并有序链表与 K 路归并第 21、23 题第 21 题 Merge Two Sorted Lists递归合并两个有序链表即上文mergeTwoLists模板时间复杂度 O(nm)。第 23 题 Merge k Sorted ListsK 路归并可采用两两归并或优先队列堆逐个取最小节点时间复杂度 O(n log k)。仓库的 structures/PriorityQueue.go 提供了堆的基础设施structures/Heap.go 定义了可复用的堆实现可用于堆化 K 个链表的头节点。六、链表归类第 86、328 题归类指按条件将链表拆成多个子链表再拼接86. Partition List按基准值将链表分为小于 x与大于等于 x两段再首尾相接328. Odd Even Linked List按下标奇偶性将节点分为奇偶两条链最后偶数链接到奇数链尾部。这类题目同样借助虚拟头结点或哨兵节点来统一拼接逻辑与第一节方法论一脉相承。七、链表排序O(n log n) 时间 O(1) 空间的唯一解是归并排序第 148 题原文档结论链表排序要求时间复杂度 O(n * log n)、空间复杂度 O(1) 时只有归并排序至顶向下一种做法。这是因为数组常用的快排依赖随机访问下标而链表无法 O(1) 定位堆排序则需要额外数组。归并排序只需修改指针即可完成天然契合链表结构。仓库完整实现见 leetcode/0148.Sort-List/148. Sort List.gofunc sortList(head *ListNode) *ListNode { length : 0 cur : head for cur ! nil { length cur cur.Next } if length 1 { return head } middleNode : middleNode(head) cur middleNode.Next middleNode.Next nil middleNode cur left : sortList(head) right : sortList(middleNode) return mergeTwoLists(left, right) }流程拆解先统计链表长度长度 ≤ 1 直接返回用快慢指针middleNode找到中点断开链表middleNode.Next nil分成左右两半递归排序左右两半用递归版mergeTwoLists合并两个有序链表。八、环形链表与相交链表第 141、142、160 题原文档给出两类判定与定位问题判断链表是否存在环快慢指针快指针每次 2 步、慢指针每次 1 步若相遇则有环第 141 题若有环输出环的交叉点下标第 142 题相遇后再走一圈即可得到环入口判断两个链表是否有交叉点若有输出交叉点第 160 题经典做法是双指针各自遍历两条链后交换路径相遇点即交点。仓库为环状链表的测试提供了现成构造工具 structures/ListNode.go 中的Ints2ListWithCycle(nums, pos)其中pos为环入口下标pos -1表示无环可直接用于验证 141/142 题的测试用例GetNodeWith(val)则用于按值定位节点。九、专题题目总览原文档通过模板占位符{{.AvailableTagTable}}在站点中渲染出完整的题目表格其数据源为 ctl/meta/Linked_List。下表整理该专题的全部 28 道题目题号、难度、复杂度均为该数据源与源码实现所记录的信息题号题目难度时间复杂度空间复杂度2Add Two NumbersMediumO(n)O(1)19Remove Nth Node From End of ListMediumO(n)O(1)21Merge Two Sorted ListsEasyO(log n)O(1)23Merge k Sorted ListsHardO(log n)O(1)24Swap Nodes in PairsMediumO(n)O(1)25Reverse Nodes in k-GroupHardO(log n)O(1)61Rotate ListMediumO(n)O(1)82Remove Duplicates from Sorted List IIMediumO(n)O(1)83Remove Duplicates from Sorted ListEasyO(n)O(1)86Partition ListMediumO(n)O(1)92Reverse Linked List IIMediumO(n)O(1)109Convert Sorted List to Binary Search TreeMediumO(log n)O(n)141Linked List CycleEasyO(n)O(1)142Linked List Cycle IIMediumO(n)O(1)143Reorder ListMediumO(n)O(1)147Insertion Sort ListMediumO(n)O(1)148Sort ListMediumO(n log n)O(n)160Intersection of Two Linked ListsEasyO(n)O(1)203Remove Linked List ElementsEasyO(n)O(1)206Reverse Linked ListEasyO(n)O(1)234Palindrome Linked ListEasyO(n)O(1)237Delete Node in a Linked ListEasyO(n)O(1)328Odd Even Linked ListMediumO(n)O(1)445Add Two Numbers IIMediumO(n)O(n)725Split Linked List in PartsMediumO(n)O(1)817Linked List ComponentsMediumO(n)O(1)707Design Linked ListEasyO(n)O(1)876Middle of the Linked ListEasyO(n)O(1)1019Next Greater Node In Linked ListMediumO(n)O(1)说明表中复杂度为专题元数据所标注个别题目的时间复杂度标注如 21 题标为 O(log n)与该题的常规理论最优略有出入以仓库 ctl/meta/Linked_List 数据为准实际解答可参考leetcode/目录下对应题号的 Go 源码与测试文件。其中带 ❤️ 标记的题目23、25、86、92、141、142、143、147、148、160、876为仓库重点推荐题。所有题目的题解源码与测试用例均位于 leetcode 目录下以题号.题目名命名的子目录中例如0019.Remove-Nth-Node-From-End-of-List0023.Merge-k-Sorted-Lists0141.Linked-List-Cycle0142.Linked-List-Cycle-II0160.Intersection-of-Two-Linked-Lists每个目录均包含题解 Go 源码、_test.go测试文件与 README 说明可用于对照学习与本地验证仓库提供了 gotest.sh 脚本便于批量运行测试。十、小结链表题的条件反射清单题目特征首选思路代表题目操作可能涉及头结点虚拟头结点92、206、203找中点 / 找倒数第 n 个节点快慢指针876、19合并两个 / K 个有序链表递归 / 堆21、23按条件拆分重组归类 拼接86、328O(n log n) 时间排序至顶向下归并排序148判断环 / 找环入口快慢指针 相遇判定141、142判断两链表相交双指针交换路径160掌握以上范式后再回到 链表专题文档 对照每一行方法论即可快速定位每道题的破题点。仓库其余专题Array、Two_Pointers、Tree 等的文档均位于 ctl/template 目录方法论体系保持一致可继续按此方法系统刷题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 链表专题虚拟头结点、递归与归并排序的题解方法论【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode-Go 仓库中 链表专题文档 展开系统梳理单链表类题目最核心的七类解题范式虚拟头结点、递归、区间逆序、快慢指针找中点/倒数第 n 个节点、K 路归并、链表归类、归并排序以及环形链表与相交链表判定。文中将结合仓库leetcode/下对应题目的 Go 实现源码逐一给出可直接复用的代码模板与复杂度结论帮助读者建立一套看到链表题就知道该往哪个方向想的解题框架。一、虚拟头结点统一遍历逻辑的关键技巧链表题最大的痛点在于边界处理当操作可能发生在头结点head身上时删除、反转、分区等逻辑都要单独判断头结点是否为空、是否被修改。虚拟头结点dummy node通过在真实头结点前额外挂一个哨兵节点让所有操作都统一为对中间节点操作从而消解边界分支。核心原则构造虚拟头结点使遍历处理逻辑更加统一。仓库中的 ListNode 定义位于 structures/ListNode.go链表的序列化/反序列化辅助函数List2Ints、Ints2List也在同一文件便于测试时构造用例type ListNode struct { Val int Next *ListNode }应用实例92. Reverse Linked List II区间逆序m 到 n 反转是虚拟头结点的经典使用场景。仓库实现见 leetcode/0092.Reverse-Linked-List-II/92. Reverse Linked List II.gofunc reverseBetween(head *ListNode, m int, n int) *ListNode { if head nil || m n { return head } newHead : ListNode{Val: 0, Next: head} pre : newHead for count : 0; pre.Next ! nil count m-1; count { pre pre.Next } if pre.Next nil { return head } cur : pre.Next for i : 0; i n-m; i { tmp : pre.Next pre.Next cur.Next cur.Next cur.Next.Next pre.Next.Next tmp } return newHead.Next }关键点在于newHead : ListNode{Val: 0, Next: head}即使m 1从头结点开始反转pre依然有前驱反转逻辑无需特判。最终返回newHead.Next即为新链表头。二、递归巧解链表但需警惕栈溢出链表天然具有递归结构Next指针指向子链表因此很多题目可以构造递归条件巧妙求解。仓库中mergeTwoLists就是一个典型递归实现见 leetcode/0148.Sort-List/148. Sort List.gofunc mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 nil { return l2 } if l2 nil { return l1 } if l1.Val l2.Val { l1.Next mergeTwoLists(l1.Next, l2) return l1 } l2.Next mergeTwoLists(l1, l2.Next) return l2 }⚠️ 注意递归深度过深会导致超时和栈溢出。对于超长链表应改用迭代版本或显式栈。这是链表题中递归虽美、但需权衡的重要边界。三、链表区间逆序第 92 题在 第一节 已经给出了 92. Reverse Linked List II 的完整实现。该方法时间复杂度 O(n)、空间复杂度 O(1)采用头插法思路用虚拟头结点定位m-1位置的节点pre固定cur : pre.Next为区间起点循环n-m次每次把cur.Next摘下来插到pre后面逐步完成区间逆序。这也是解决 25. Reverse Nodes in k-Group 的前置技能。四、快慢指针一次遍历找中间节点与倒数第 n 个节点链表无法随机访问但可以用快慢指针在一次遍历内解决问题寻找中间节点慢指针每次走 1 步快指针每次走 2 步快指针到末尾时慢指针恰在中点附近对应第 876 题寻找倒数第 n 个节点让快指针先走 n 步再让快慢指针同步前进快指针到达末尾时慢指针即为倒数第 n 个节点对应第 19 题。876. Middle of the Linked List 仓库实现见 leetcode/0876.Middle-of-the-Linked-List/876. Middle of the Linked List.gofunc middleNode(head *ListNode) *ListNode { if head nil || head.Next nil { return head } p1 : head p2 : head for p2.Next ! nil p2.Next.Next ! nil { p1 p1.Next p2 p2.Next.Next } length : 0 cur : head for cur ! nil { length cur cur.Next } if length%2 0 { return p1.Next } return p1 }注意偶数长度时中点的取法题目要求返回第二个中间节点因此代码先统计链表长度偶数时返回p1.Next。这也是 148. Sort List 归并排序找切分点的核心依赖。五、合并有序链表与 K 路归并第 21、23 题第 21 题 Merge Two Sorted Lists递归合并两个有序链表即上文mergeTwoLists模板时间复杂度 O(nm)。第 23 题 Merge k Sorted ListsK 路归并可采用两两归并或优先队列堆逐个取最小节点时间复杂度 O(n log k)。仓库的 structures/PriorityQueue.go 提供了堆的基础设施structures/Heap.go 定义了可复用的堆实现可用于堆化 K 个链表的头节点。六、链表归类第 86、328 题归类指按条件将链表拆成多个子链表再拼接86. Partition List按基准值将链表分为小于 x与大于等于 x两段再首尾相接328. Odd Even Linked List按下标奇偶性将节点分为奇偶两条链最后偶数链接到奇数链尾部。这类题目同样借助虚拟头结点或哨兵节点来统一拼接逻辑与第一节方法论一脉相承。七、链表排序O(n log n) 时间 O(1) 空间的唯一解是归并排序第 148 题原文档结论链表排序要求时间复杂度 O(n * log n)、空间复杂度 O(1) 时只有归并排序至顶向下一种做法。这是因为数组常用的快排依赖随机访问下标而链表无法 O(1) 定位堆排序则需要额外数组。归并排序只需修改指针即可完成天然契合链表结构。仓库完整实现见 leetcode/0148.Sort-List/148. Sort List.gofunc sortList(head *ListNode) *ListNode { length : 0 cur : head for cur ! nil { length cur cur.Next } if length 1 { return head } middleNode : middleNode(head) cur middleNode.Next middleNode.Next nil middleNode cur left : sortList(head) right : sortList(middleNode) return mergeTwoLists(left, right) }流程拆解先统计链表长度长度 ≤ 1 直接返回用快慢指针middleNode找到中点断开链表middleNode.Next nil分成左右两半递归排序左右两半用递归版mergeTwoLists合并两个有序链表。八、环形链表与相交链表第 141、142、160 题原文档给出两类判定与定位问题判断链表是否存在环快慢指针快指针每次 2 步、慢指针每次 1 步若相遇则有环第 141 题若有环输出环的交叉点下标第 142 题相遇后再走一圈即可得到环入口判断两个链表是否有交叉点若有输出交叉点第 160 题经典做法是双指针各自遍历两条链后交换路径相遇点即交点。仓库为环状链表的测试提供了现成构造工具 structures/ListNode.go 中的Ints2ListWithCycle(nums, pos)其中pos为环入口下标pos -1表示无环可直接用于验证 141/142 题的测试用例GetNodeWith(val)则用于按值定位节点。九、专题题目总览原文档通过模板占位符{{.AvailableTagTable}}在站点中渲染出完整的题目表格其数据源为 ctl/meta/Linked_List。下表整理该专题的全部 28 道题目题号、难度、复杂度均为该数据源与源码实现所记录的信息题号题目难度时间复杂度空间复杂度2Add Two NumbersMediumO(n)O(1)19Remove Nth Node From End of ListMediumO(n)O(1)21Merge Two Sorted ListsEasyO(log n)O(1)23Merge k Sorted ListsHardO(log n)O(1)24Swap Nodes in PairsMediumO(n)O(1)25Reverse Nodes in k-GroupHardO(log n)O(1)61Rotate ListMediumO(n)O(1)82Remove Duplicates from Sorted List IIMediumO(n)O(1)83Remove Duplicates from Sorted ListEasyO(n)O(1)86Partition ListMediumO(n)O(1)92Reverse Linked List IIMediumO(n)O(1)109Convert Sorted List to Binary Search TreeMediumO(log n)O(n)141Linked List CycleEasyO(n)O(1)142Linked List Cycle IIMediumO(n)O(1)143Reorder ListMediumO(n)O(1)147Insertion Sort ListMediumO(n)O(1)148Sort ListMediumO(n log n)O(n)160Intersection of Two Linked ListsEasyO(n)O(1)203Remove Linked List ElementsEasyO(n)O(1)206Reverse Linked ListEasyO(n)O(1)234Palindrome Linked ListEasyO(n)O(1)237Delete Node in a Linked ListEasyO(n)O(1)328Odd Even Linked ListMediumO(n)O(1)445Add Two Numbers IIMediumO(n)O(n)725Split Linked List in PartsMediumO(n)O(1)817Linked List ComponentsMediumO(n)O(1)707Design Linked ListEasyO(n)O(1)876Middle of the Linked ListEasyO(n)O(1)1019Next Greater Node In Linked ListMediumO(n)O(1)说明表中复杂度为专题元数据所标注个别题目的时间复杂度标注如 21 题标为 O(log n)与该题的常规理论最优略有出入以仓库 ctl/meta/Linked_List 数据为准实际解答可参考leetcode/目录下对应题号的 Go 源码与测试文件。其中带 ❤️ 标记的题目23、25、86、92、141、142、143、147、148、160、876为仓库重点推荐题。所有题目的题解源码与测试用例均位于 leetcode 目录下以题号.题目名命名的子目录中例如0019.Remove-Nth-Node-From-End-of-List0023.Merge-k-Sorted-Lists0141.Linked-List-Cycle0142.Linked-List-Cycle-II0160.Intersection-of-Two-Linked-Lists每个目录均包含题解 Go 源码、_test.go测试文件与 README 说明可用于对照学习与本地验证仓库提供了 gotest.sh 脚本便于批量运行测试。十、小结链表题的条件反射清单题目特征首选思路代表题目操作可能涉及头结点虚拟头结点92、206、203找中点 / 找倒数第 n 个节点快慢指针876、19合并两个 / K 个有序链表递归 / 堆21、23按条件拆分重组归类 拼接86、328O(n log n) 时间排序至顶向下归并排序148判断环 / 找环入口快慢指针 相遇判定141、142判断两链表相交双指针交换路径160掌握以上范式后再回到 链表专题文档 对照每一行方法论即可快速定位每道题的破题点。仓库其余专题Array、Two_Pointers、Tree 等的文档均位于 ctl/template 目录方法论体系保持一致可继续按此方法系统刷题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
到底创建了几个对象？)
