LeetCode Reorder Linked List（143）题解：快慢指针拆半 + 反转合并的 O(n)/O(1) 原地重排方案

LeetCode Reorder Linked List143题解快慢指针拆半 反转合并的 O(n)/O(1) 原地重排方案【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕本仓库中 hints/reorder-linked-list.md 与 articles/reorder-linked-list.md 两个核心文档系统讲解 LeetCode 143「重排链表」问题的完整解法体系从暴力法的O(n)空间实现到快慢指针定位中点、反转后半段、交替合并的O(n)时间 /O(1)空间原地解法。读完本文你将掌握链表找中点 — 反转 — 交错合并三段式模板并能直接对照本仓库 python/0143-reorder-list.py、java/0143-reorder-list.java 等 12 种语言的实现进行练习验证。1. 问题定义什么是重排链表给定单链表头节点head要求将链表原地重排为如下模式L0 → Ln → L1 → L(n−1) → L2 → L(n−2) → ...例如输入[1, 2, 3, 4]输出[1, 4, 2, 3]输入[1, 2, 3, 4, 5]输出[1, 5, 2, 4, 3]题目的核心约束是不允许修改节点值只能通过调整next指针完成即真正的原地重排如 typescript/0143-reorder-list.ts 头部注释所述Do not return anything, modify head in-place instead。这也是链表类题目最典型的考点指针的保存、断开与重连。2. 复杂度目标为什么是 O(n) 时间与 O(1) 空间hints/reorder-linked-list.md 开篇明确给出了推荐目标You should aim for a solution withO(n)time andO(1)space, wherenis the length of the given list.即指标目标值说明时间复杂度O(n)链表只需常数次完整遍历找中点一次、反转一次、合并一次空间复杂度O(1)除若干指针变量外不申请额外数据结构该 hint 文档同时给出了解题的三个递进提示详见下文第 3、5 节而 articles/reorder-linked-list.md 则给出了三种从易到难的完整实现其中只有第三种拆半 反转 合并同时满足上述两个目标。3. 方法一暴力解法数组 双指针3.1 思路hint 1 指出暴力解法是把节点值存进数组、重排后再建新链表并追问能否原地完成。虽然可以进一步优化到只存节点引用而非值直接在原链表上改指针但它仍然消耗O(n)的额外空间遍历链表将所有节点按序存入数组nodes双指针i 0头、j len(nodes) - 1尾循环i jnodes[i].next nodes[j]i若i j则跳出nodes[j].next nodes[i]j--循环结束后nodes[i].next None收尾防止成环。3.2 参考实现Pythonclass Solution: def reorderList(self, head: Optional[ListNode]) - None: if not head: return nodes [] cur head while cur: nodes.append(cur) cur cur.next i, j 0, len(nodes) - 1 while i j: nodes[i].next nodes[j] i 1 if i j: break nodes[j].next nodes[i] j - 1 nodes[i].next None3.3 复杂度时间复杂度O(n)一次收集 一次双指针重排空间复杂度O(n)数组存了全部 n 个节点适用场景作为面试的保底答案快速讲出在允许O(n)空间或链表长度很小如 Rust 的OptionBoxListNode所有权模型不便直接改指针时也是合理选择——本仓库的 rust/0143-reorder-list.rs 采用的就是先收集值再回写的变体。4. 方法二递归法O(n) 空间4.1 思路articles/reorder-linked-list.md 还收录了一种递归写法利用递归天然先深入尾部、再回溯的特性在回溯阶段把尾部节点与头部节点两两配对定义rec(root, cur)cur通过递归到达链表尾部root是当前待配对的前端节点基准情形cur为None时返回root回溯时若root cur或root.next cur两指针相遇或相邻置cur.next None结束否则保存tmp root.next令root.next cur、cur.next tmp返回tmp作为新的前端指针。4.2 参考实现Pythonclass Solution: def reorderList(self, head: Optional[ListNode]) - None: def rec(root: ListNode, cur: ListNode) - ListNode: if not cur: return root root rec(root, cur.next) if not root: return None tmp None if root cur or root.next cur: cur.next None else: tmp root.next root.next cur cur.next tmp return tmp head rec(head, head.next)4.3 复杂度与评价时间复杂度O(n)空间复杂度O(n)递归调用栈深度该方法逻辑优雅但并非最优且对超长链表有栈溢出风险因此仅作为思路补充面试中优先推荐第 5 节的迭代三段式。5. 方法三最优快慢指针拆半 反转 交替合并这是 hint 2 与 hint 3 共同指向的官方推荐方案也是本仓库绝大多数语言实现采用的标准解如 python/0143-reorder-list.py、java/0143-reorder-list.java、go/0143-reorder-list.go。5.1 核心思路以[1, 2, 3, 4, 5]为例目标等价于把链表切成两半前半保持[1, 2]后半反转成[5, 4, 3]再把二者交错合并为1 → 5 → 2 → 4 → 3。整个流程分三步找中点快慢指针slow每次走一步、fast每次走两步fast到达链表末尾时slow恰好停在前半段的最后一个节点hint 3 明确推荐此方法。反转第二半从slow.next开始用标准的prev / tmp三指针法原地反转并把slow.next置空彻底断开两半。交替合并同时遍历两个链表先取一个前半节点再取一个反转后的后半节点循环直至后半耗尽。5.2 完整参考实现Pythonclass Solution: def reorderList(self, head: Optional[ListNode]) - None: # Step 1: find the middle slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next # Step 2: reverse the second half second slow.next prev slow.next None while second: tmp second.next second.next prev prev second second tmp # Step 3: merge the two halves first, second head, prev while second: tmp1, tmp2 first.next, second.next first.next second second.next tmp1 first, second tmp1, tmp25.3 关键实现细节剖析细节一fast的初始化决定中点归属。仓库各语言中Python / Java / Go / TypeScript 采用slow head, fast head.next如 go/0143-reorder-list.go此时循环结束后slow恰好是前半段的最后一个节点slow.next即第二半头节点而 C / C 采用fast head并额外维护prev指针见 c/0143-reorder-list.c效果等价。两种写法都正确但混用时极易产生差一错误off-by-one。细节二必须显式断链。反转前先执行slow.next None或 C 版中的prev-next NULL把链表拆成两条独立链。漏掉这一步反转后第二半的尾指针会指回第一半合并时必然成环死循环。细节三合并时先保存后继。合并循环中tmp1 first.next、tmp2 second.next必须先于指针改写保存否则first.next second会覆盖掉first原来的后继导致后半段丢失java/0143-reorder-list.java 中体现得非常清楚。5.4 复杂度时间复杂度O(n)三次线性遍历常数系数小空间复杂度O(1)仅使用若干指针变量这正是 hints/reorder-linked-list.md 要求的O(n)time andO(1)space 目标解。6. 常见陷阱与边界情况articles/reorder-linked-list.md 末尾专门总结了三个高频踩坑点这里结合源码逐一说明中点定位差一错误slow/fast的初始化方式head.next还是head直接决定slow停在前半末尾还是第二半开头。选错会导致两半长度失衡重排结果错乱。忘记断开两半必须在反转前slow.next NoneC/C 为prev-next NULL见 c/0143-reorder-list.c。否则反转后链表成环合并阶段死循环。合并时丢失引用改写first.next/second.next之前必须先保存tmp1、tmp2。这是链表指针操作最容易犯的错误也是本题真正的考点。此外还要注意边界输入空链表、单节点链表直接返回如 cpp/0143-reorder-list.cpp 先判断head-next NULL两节点链表中点即头节点反转合并后自然得到正确结果奇数/偶数长度[1,2,3,4,5]后半[5,4,3]比前半多一个节点合并循环以second为条件恰好处理这种长度差。7. 仓库多语言实现对照本仓库对本题提供了 12 种语言的实现核心逻辑找中点 → 反转 → 合并完全一致可作为学习与交叉验证的素材语言实现文件实现要点Pythonpython/0143-reorder-list.py三指针原地反转与本文 5.2 节一致Javajava/0143-reorder-list.java标准 slow/fast prev/tmp 反转Ccpp/0143-reorder-list.cpp拆分为reverse与merge两个辅助函数Cc/0143-reorder-list.c用prev记录中点前驱merge内判断p1 NULL收尾Gogo/0143-reorder-list.go抽离reverse工具函数主流程清晰JavaScriptjavascript/0143-reorder-list.js同三段式注意null判空TypeScripttypescript/0143-reorder-list.ts类型标注ListNode \| null空指针防护C#csharp/0143-reorder-list.cs同 Java 结构Kotlinkotlin/0143-reorder-list.ktKotlin 可空类型 ?:安全调用Swiftswift/0143-reorder-list.swiftSwift 可空链式调用Rustrust/0143-reorder-list.rs受所有权模型限制改用统计长度 取中点 take()断链 std::mem::swap合并注释中亦有说明Scalascala/0143-reorder-list.scala函数式风格实现其中 Rust 版本是值得一提的工程特例由于OptionBoxListNode的所有权约束它先统计链表总长度、按长度定位中点再用node.next.take()优雅地取出并断开第二半最后借助std::mem::swap完成原地交替合并——思路与三段式一致但更贴合 Rust 的所有权语义见 rust/0143-reorder-list.rs。8. 总结重排链表LeetCode 143是一道将链表三大基本功——快慢指针找中点、原地反转、交错合并——串联于一体的经典题目也是面试高频题。解题路线可归纳为先讲暴力数组存节点 双指针重排O(n)空间作为正确性兜底再讲递归O(n)栈空间展示对递归回溯的理解最后给出最优解快慢指针拆半 → 反转第二半 → 交替合并O(n)时间、O(1)空间并强调断链与保存后继两个关键细节。建议在本地对照 python/0143-reorder-list.py 等仓库实现手写一遍并用[1,2,3,4]、[1,2,3,4,5]、单节点与空链表四组用例自测即可牢固掌握这套模板。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考