LeetCode-Go 题解精讲0143.Reorder List 链表重排的两种解法O(1) 空间原地实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 143 题「重排链表Reorder List」展开以 0143.Reorder-List.md 为讲解主线结合 LeetCode-Go 仓库中 143. Reorder List.go 的完整实现与 143. Reorder List_test.go 的测试用例深入剖析两种解题方案空间复杂度 O(n) 的数组辅助法和空间复杂度 O(1) 的「找中点 反转后半段 双指针拼接」原地法。读完本文你将掌握链表三连技巧快慢指针找中点、区间反转、指针重连的组合运用并能直接在本地运行仓库中的测试验证结果。题目回顾重排规则与硬性约束题目要求对一个单链表 L: L0→L1→…→Ln-1→Ln 进行重排目标形态为L0→Ln→L1→Ln-1→L2→Ln-2→…即第一个元素与最后一个元素相邻第二个元素与倒数第二个元素相邻依此类推首尾交替穿插。关键约束不得修改链表节点的数值You may not modify the values in the lists nodes只能通过调整节点之间的指针关系来改变结构。两个官方示例给定 1-2-3-4重排为 1-4-2-3。 给定 1-2-3-4-5重排为 1-5-2-4-3。从示例可以看出偶数长度时前半段与后半段严格穿插奇数长度时最中间的节点自然落在结果末尾如 5 个节点时中间的 3 成为末尾。解法一数组辅助法 —— O(n) 时间、O(n) 空间核心思想原文档指出最简单的思路是先把链表完整存储到一个数组里再按规则重新拼接。因为数组支持 O(1) 的随机访问可以轻松拿到任意位置的节点尤其是从尾部倒数第 i 个节点从而绕开单链表只能单向遍历的限制。源码实现逐行解读仓库 143. Reorder List.go 中reorderList1实现了该方案// 解法二 数组 func reorderList1(head *ListNode) *ListNode { array : listToArray(head) length : len(array) if length 0 { return head } cur : head last : head for i : 0; i len(array)/2; i { tmp : ListNode{Val: array[length-1-i], Next: cur.Next} cur.Next tmp cur tmp.Next last tmp } if length%2 0 { last.Next nil } else { cur.Next nil } return head } func listToArray(head *ListNode) []int { array : []int{} if head nil { return array } cur : head for cur ! nil { array append(array, cur.Val) cur cur.Next } return array }解析如下链表转数组listToArray从头到尾遍历一次链表把每个节点的Val依序压入[]int时间复杂度 O(n)。循环穿插for i : 0; i len(array)/2; i只遍历前半段。每次循环中用array[length-1-i]对应原链表倒数第 i1 个元素新建一个节点并把它插入到cur之后随后cur前进到新节点的Next即原顺序的下一个节点。收尾处理循环结束后需要切断多余的尾部指针否则会出现环或多余节点残留链表长度为偶数时last.Next nil收尾链表长度为奇数时cur.Next nil收尾。复杂度与局限时间复杂度O(n)其中 n 为链表长度遍历数组 新建节点。空间复杂度O(n)[]int数组需要额外存储全部节点值同时每插入一个「尾部节点」都new出一个新节点实际额外分配的对象数量也是 O(n/2)。该方案胜在直观、不易出错但额外数组与新建节点使其空间开销偏高并非题目期望的「最优解」。需要注意它与「不允许修改节点值、只能改指针」的约束并不冲突——它同样是新建节点并调整指针只是以空间换取了实现的简单性。解法二原地重排法 —— O(n) 时间、O(1) 空间核心思想原文档指出更好的做法是复用链表领域的经典操作组合先找中间结点再反转后半段链表最后用两个指针从头尾两侧开始拼接。这正好呼应了仓库中已有的两道前置题目找中点快慢指针slow/fast慢指针每次走一步、快指针每次走两步区间反转参考 第 92 题 Reverse Linked List II 中reverseBetween()的区间反转思路只不过本题的反转区间是从中点一直延伸到链表末尾。整条链路的时间复杂度为 O(n)空间复杂度为 O(1)只用了常数个指针变量是本题的标准最优解。三步走从 1-2-3-4-5-6 到 1-6-2-5-3-4仓库 143. Reorder List.go 中reorderList的实现分三步第一步快慢指针寻找中间结点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 }p1是慢指针、p2是快指针循环条件p2.Next ! nil p2.Next.Next ! nil保证快指针不会越界循环结束时p1恰好停在链表的中间位置偶数长度时偏左例如 6 个节点时p1指向 3。第二步原地反转中点之后的链表// 反转链表后半部分 1-2-3-4-5-6 to 1-2-3-6-5-4 preMiddle : p1 preCurrent : p1.Next for preCurrent.Next ! nil { current : preCurrent.Next preCurrent.Next current.Next current.Next preMiddle.Next preMiddle.Next current }这段循环是标准的「头插法」区间反转等价于 第 92 题 中reverseBetween()的原地翻转手法preMiddle固定指向中点相当于区间头的前驱preCurrent从preMiddle.Next后半段第一个节点开始每轮循环把currentpreCurrent.Next摘出来插入到preMiddle之后效果示例1-2-3-4-5-6翻转为1-2-3-6-5-4。第三步双指针首尾交替拼接// 重新拼接链表 1-2-3-6-5-4 to 1-6-2-5-3-4 p1 head p2 preMiddle.Next for p1 ! preMiddle { preMiddle.Next p2.Next p2.Next p1.Next p1.Next p2 p1 p2.Next p2 preMiddle.Next } return headp1指向头结点p2指向反转后后半段的首节点即原链表的尾节点循环条件p1 ! preMiddle由于偶数长度时中点偏左preMiddle恰好是前半段的最后一个节点拼接到中点前即可停止不会产生环每轮做四步指针操作先把p2从后半段链表中摘出preMiddle.Next p2.Next再让p2指向p1的下一个节点并插入p2.Next p1.Next; p1.Next p2最后p1跳到刚插入节点的后继、p2取回后半段新头部效果示例1-2-3-6-5-4拼接为1-6-2-5-3-4与原题目要求完全一致。与第 92 题 reverseBetween 的关联原文档特别提到本题第二步可以借鉴 Problem 92 的reverseBetween()。对比两段代码可以发现同一套「头插反转」内核// 92 题 reverseBetween 中的核心循环 for i : 0; i n-m; i { tmp : pre.Next pre.Next cur.Next cur.Next cur.Next.Next pre.Next.Next tmp }两者的区别仅在于92 题的反转区间由参数m、n显式指定而本题的反转区间是「中点 → 末尾」属于 92 题区间反转的特例化应用。这也印证了原文档「结合之前几道题的操作」的说法——链表题的高效解往往是由若干经典原子操作组合而成。测试用例与本地验证仓库为本题配备了完整的表驱动测试见 143. Reorder List_test.gofunc Test_Problem143(t *testing.T) { qs : []question143{ { para143{[]int{1, 2, 3, 4, 5}}, ans143{[]int{1, 5, 2, 4, 3}}, }, { para143{[]int{1, 2, 3, 4}}, ans143{[]int{1, 4, 2, 3}}, }, { para143{[]int{1}}, ans143{[]int{1}}, }, { para143{[]int{}}, ans143{[]int{}}, }, } // ... }测试覆盖了四种典型输入奇数长度5 个节点、偶数长度4 个节点、单节点、空链表与题目给出的官方示例吻合同时验证了边界情况下的正确性不会 panic、不会产生环。测试中还复用了 structures/ListNode.go 提供的链表工具函数Ints2List(nums []int) *ListNode把[]int转换为链表ListNode.goList2Ints(head *ListNode) []int把链表还原为[]int且内置了 100 层深度限制遇到环状链表会主动 panic 以提示错误ListNode.go。ListNode类型本身定义在 structures/ListNode.go通过type ListNode structures.ListNode在题解文件中以类型别名方式引用见 143. Reorder List.go。本地运行测试的命令如下在仓库根目录执行# 只跑第 143 题的测试 go test -v ./leetcode/0143.Reorder-List/... # 或者运行整个仓库的测试并生成覆盖率见 gotest.sh go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库 gotest.sh 展示了第二种批量执行方式对./leetcode/...一次性执行带-covermodeatomic的测试并输出coverage.txt这也是本仓库保证「100% test coverage」的常规验证流程。两种解法对比与边界情况小结维度解法一数组辅助解法二原地重排时间复杂度O(n)O(n)空间复杂度O(n)需额外数组与新建节点O(1)仅常数个指针实现难度简单直观中等需理解指针重连是否修改节点值否否适用场景追求可读性与快速 AC面试/竞赛标准最优解边界情况处理要点空链表 / 单节点解法二在入口处直接if head nil || head.Next nil { return head }短路返回解法一通过length 0判空测试用例中的[]int{1}与[]int{}正是为验证这两个分支。偶数长度快慢指针停在偏左的中点拼接循环在p1 ! preMiddle处终止保证结果无环、无多余节点残留。防环设计解法二始终在原链表节点上重排、不做复制解法一在循环后显式切断尾部last.Next nil/cur.Next nil防止残留指针形成环。延伸阅读本题英文原题文档0143.Reorder-List.md前置知识点 1 —— 区间反转0092.Reverse-Linked-List-II 题解前置知识点 2 —— 快慢指针与中点查找可对照仓库中链表类题目的通用套路如 0876.Middle-of-the-Linked-List公共链表结构与工具函数structures/ListNode.go仓库全局题解索引README_zh.md【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考