双指针与滑动窗口 · HTML
数学 / 逻辑形态
每次改写 cur.next 前先保存 nxt=cur.next；改线后更新已处理链和未处理链的边界。dummy 节点把头部操作统一为普通后继操作。
识别信号
- 输入是 singly linked list，要求 in-place。
- 操作会改变节点顺序或删除某节点。
- 随机访问不可用，只能沿 next 前进。
- 头节点可能变化，边界分支很多。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 只读链表遍历 | 若只统计值，不必改线；普通快慢指针或单指针即可。 |
| 需要按索引频繁访问 | 链表不适合随机定位，转数组可能更合理。 |
核心不变量
prev 是已处理链的正确头/尾边界，cur 是未处理链首节点；所有节点始终恰属于其中一侧且无丢失。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | dummy（可选）、prev、cur、nxt，以及操作特有的 segment head/tail。 |
| Transition | 保存 nxt，重写 cur.next 指向新位置，再推进 prev=cur、cur=nxt。 |
| Frontier / order | 已重连前缀与尚保持原结构后缀之间的一条 next 边界。 |
Python 骨架
def reverse_list(head):
prev, cur = None, head
while cur is not None:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
正确性思路
- 保存 nxt 后，未处理后缀仍可达，不会因改写 cur.next 丢失。
- 每轮把 cur 从原后缀首移到正确反转前缀首，维持分割不变量。
- cur 为空时所有节点均进入反转前缀，prev 即新头，且每条 next 方向正确。
复杂度
| Time | Space | Parameters |
|---|
| O(n) | O(1) | n 为被处理节点数；每节点的 next 改写常数次。 |
边界条件
- 空链表返回 None。
- 单节点 next 仍为 None。
- 删除头节点时 dummy 能避免特殊分支。
- 输入若可能有环，普通 while cur 会无限循环，先明确前置条件。
错误模式
| Pattern | Why it fails / fix |
|---|
| 先改 next 后保存后继 | 会永久丢失未处理链。 |
| 返回旧 head | 完整反转后新头是 prev。 |
| 局部反转后未接回两端 | 要同时保存段前节点与段后节点。 |
选择与排除规则
- 头节点可能改变：先画 dummy。
- 每次落笔改 next 前先写 nxt=cur.next。
- 复杂重排先标出各段 head/tail，再决定连接顺序。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 返回 c，得到 c→b→a→None。 |
| Setup | 链 a→b→c→None。 |
| Trace | a 指向 None，b 指向 a，c 指向 b；每步先保存原后继。 |
Recall prompts
我的补充