第4章｜链表
Unit 02 · LeetCode #206 反转链表
反转链表的难点，不是“让箭头朝左”，
而是改边之前不能丢失未处理区域。
上一单元通过前驱节点绕过目标节点；这一单元继续修改 next，但要逐条反转所有边。每轮都必须严格执行：保存后继 → 反转当前边 → 移动两个指针。
题目要求
给定单链表的头节点 head，反转链表，并返回反转后的链表头节点。
输入、输出与约束
- 输入：单链表头节点
head；输出：反转后的新头节点。 - 节点数范围：0–5000；节点值范围：-5000–5000。
- 目标复杂度：
O(n)时间，迭代版本O(1)额外空间。
示例
输出：[5,4,3,2,1]
输出：[2,1]
输出：[]
本页主方法
使用 previous / current / next_node。主动画采用显式迭代，因为它把“保存后继”和“修改边”的因果顺序完整暴露出来。
先连接上一题：#203 与 #206 都在改写 next，但修改目标不同
current.next = current.next.next
绕过一个节点，前驱通常保持不动。
current.next = previous
改变当前节点的出边方向，必须先保存原后继。
已反转区域的头节点。开始时为空；循环结束时成为整条反转链表的新头。
未处理区域的第一个节点，也是本轮即将改变 next 的节点。
修改 current.next 前保存的原后继。它维持通往剩余链表的唯一入口。
任意时刻，全部节点应当能从 previous、current 或临时 next_node 中被找到，不能永久失联。
错误 1：先反转，再找后继
current.next 已被覆盖，后续链表入口丢失。
但没有变量继续指向 n2
错误 2：移动顺序相反
若先令 current = next_node，再写 previous = current，previous 会跳到未处理节点。
再：current = saved next
错误 3：返回原 head
反转后原 head 已变成尾节点，且其 next 为 None。
返回 previous → [4,3,2,1]
迁移题：LeetCode #234 回文链表
本次迁移不从完整代码开始，而是先读官方原题，再判断哪些模块来自 Unit 02、哪些是新加入的。核心路线是：快慢指针找中点 → 原地反转后半段 → 同步比较两半。
阶段 1：先确认官方题目到底要求什么
官方题意
给定单链表头节点 head，判断该链表的节点值序列是否构成回文。回文意味着从前向后与从后向前读取完全相同。
进阶目标
使用 O(n) 时间与 O(1) 额外空间完成判断。
官方示例
输出：true
输出：false
官方约束
- 节点数在
[1, 10⁵]； 0 ≤ Node.val ≤ 9；- 返回布尔值，不返回反转后的链表。
答案是 True / False，不是链表或中点。
单链表不能从尾部向前读取，需要制造可比较方向。
不能把所有值复制到数组后再双指针比较。
反转后半段后，两半都能沿 next 向前读取。
阶段 2：#206 是反转模块，#234 是三个模块的组合
| 维度 | #206 反转链表 | #234 回文链表 |
|---|---|---|
| 最终目标 | 返回整条链表的新头 | 返回节点值是否前后对称 |
| 已知模块 | reverse(head) | 把 reverse 用在后半段 |
| 新增状态 | previous/current/next_node | slow/fast 找中点，first/second 比较 |
| 结构修改 | 反转全部 next 边 | 只反转后半段，比较时只读 val |
| 复杂度 | O(n) / O(1) | O(n) / O(1) |
请按真实执行顺序点击三个模块。顺序错误时可以重置后重试。
reverse(slow) 后，slow 在反转函数内部扮演什么角色？阶段 3：只填写四个新增语义，不重新发明 reverse
反转辅助函数沿用 Unit 02。这里重点补充 #234 新增的“中点、调用位置、比较与返回”语义。
from typing import Optional
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def reverse(start):
previous = None
current = start
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = reverse(slow)
first = head
while second:
if first.val != second.val:
return False
first = first.next
second = second.next
return True
阶段 4：运行官方样例 [1,2,2,1]，再独立重写
不要复制组装代码。独立写出找中点、反转后半段和比较两半。
#206 → #234 迁移结论
迁移并不是把整题重新背一遍，而是把稳定的 reverse Skill 嵌入新流程。新增知识只有两块：快慢指针确定后半段入口，以及两条正向链表的同步比较。
Unit 02 Skill：在保持剩余区域可达的前提下逐条反转边
每轮先保存 next_node = current.next，再令 current.next = previous，随后依次移动 previous 和 current。循环结束时 current 为 None，previous 指向新头节点。
不会自动进入 Unit 03。可以继续调整答案框、回看任何阶段，刷新后仍恢复当前位置。