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

LeetCode Reorder Linked List（143）题解：快慢指针拆半 + 反转合并的 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 < j：
- nodes[i].next = nodes[j]，i++；
- 若i >= j则跳出；
- nodes[j].next = nodes[i]，j--；
循环结束后nodes[i].next = None收尾，防止成环。

3.2 参考实现（Python）

class 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 = None

3.3 复杂度

时间复杂度：O(n)（一次收集 + 一次双指针重排）
空间复杂度：O(n)（数组存了全部 n 个节点）

适用场景：作为面试的"保底答案"快速讲出；在允许O(n)空间或链表长度很小（如 Rust 的Option<Box<ListNode>>所有权模型不便直接改指针）时也是合理选择——本仓库的 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 参考实现（Python）

class 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 完整参考实现（Python）

class 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, tmp2

5.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 = None（C/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 种语言的实现，核心逻辑（找中点 → 反转 → 合并）完全一致，可作为学习与交叉验证的素材：

语言	实现文件	实现要点
Python	python/0143-reorder-list.py	三指针原地反转，与本文 5.2 节一致
Java	java/0143-reorder-list.java	标准 slow/fast + prev/tmp 反转
C++	cpp/0143-reorder-list.cpp	拆分为`reverse`与`merge`两个辅助函数
C	c/0143-reorder-list.c	用`prev`记录中点前驱，`merge`内判断`p1 == NULL`收尾
Go	go/0143-reorder-list.go	抽离`reverse`工具函数，主流程清晰
JavaScript	javascript/0143-reorder-list.js	同三段式，注意`null`判空
TypeScript	typescript/0143-reorder-list.ts	类型标注`ListNode \\| null`，空指针防护
C#	csharp/0143-reorder-list.cs	同 Java 结构
Kotlin	kotlin/0143-reorder-list.kt	Kotlin 可空类型 +`?:`安全调用
Swift	swift/0143-reorder-list.swift	Swift 可空链式调用
Rust	rust/0143-reorder-list.rs	受所有权模型限制改用"统计长度 + 取中点 +`take()`断链 +`std::mem::swap`合并"，注释中亦有说明
Scala	scala/0143-reorder-list.scala	函数式风格实现

其中 Rust 版本是值得一提的工程特例：由于Option<Box<ListNode>>的所有权约束，它先统计链表总长度、按长度定位中点，再用node.next.take()优雅地"取出并断开"第二半，最后借助std::mem::swap完成原地交替合并——思路与三段式一致，但更贴合 Rust 的所有权语义（见 rust/0143-reorder-list.rs）。