链表 · 反转族
从 LC 206 反转链表出发，用三指针迭代法把递归压到 O(1) 空间。
1. 核心原理
链表反转（list reversal）要解决的问题模板长这样："给定一个单链表，把它的 next 指针方向全部或部分反转，再把改完的段重新接回原链"——整条反转、区间反转、k 个一组反转，骨架都是同一套指针重定向。和数组反转不同，链表只能单向走，没有"上一个"的引用，改 next 之前必须先把原 next 缓存下来，否则就丢失了走下去的唯一线索。
反转的等价定义
把"反转"看成一个变换 R：原链 a₁ → a₂ → ... → aₙ 变成 aₙ → aₙ₋₁ → ... → a₁。对每一对相邻节点 (aᵢ, aᵢ₊₁)，原本 aᵢ.next = aᵢ₊₁，反转后 aᵢ₊₁.next = aᵢ。
顺序扫描原链 a₁, a₂, ..., aₙ 时，在扫到 aᵢ 这一步要做的事是把 aᵢ.next 从"原来的 aᵢ₊₁"改成"原来的 aᵢ₋₁"——即把它的 next 指针从"指向后继"改成"指向前驱"。
这里存在时序冲突：一旦把 aᵢ.next 改掉，就丢失了访问 aᵢ₊₁ 的唯一线索。所以必须先缓存 aᵢ₊₁，再改 aᵢ.next。这是三指针迭代里 next = cur.next 必须放在 cur.next = prev 之前的原因。
三指针滑动
把反转拆成"对每个节点重定向它的 next 指针"。每步只需要三个游标：
prev：当前节点反转后应该指向的目标（原链里的前驱）cur：正在处理的节点nxt：原链里cur的下一个，暂存起来——一旦cur.next = prev改掉，就找不回原 next
每轮四步：缓存 nxt = cur.next → 重定向 cur.next = prev → 滑动 prev = cur → 滑动 cur = nxt。整个过程只用三个指针变量，空间 O(1)。
三种实现方式的对比
链表反转有三套等价写法。三种都能 O(n) 时间完成，差别在空间和适用场景：
| 方式 | 时间 | 空间 | 推广性 |
|---|---|---|---|
| 递归（"假设后面已反转再处理头节点"的子问题分解） | O(n) | O(n) 栈 | 代码短，长链容易爆栈 |
| 三指针迭代 | O(n) | O(1) | 标准模板，工程首选 |
| 头插法（dummy + 每次把节点插到 dummy 之后） | O(n) | O(1) | 反转区间 / k 个一组的最佳选择 |
递归版的子问题是"假设 reverse(head.next) 已经把后面反转好，并返回新头 newHead，原链 head.next 现在变成反转段的尾巴，只需 head.next.next = head 把 head 接到尾后，再把 head.next = null 防止成环"。表达式简洁但递归栈深度等于链表长度，Python 默认 1000 层、Java 栈通常一两 MB，长链直接 stack overflow。工程上首选三指针迭代。
推广到区间反转与分组反转
LC 206 是"反转整条链"，更一般的问题是"反转下标 [left, right] 这一段，前后两段保持原样"。三指针迭代可以直接套——找到 left 的前驱 p_prev，从 left 这个节点开始用三指针迭代反转 right - left + 1 步，最后把反转后的段重新接回 p_prev 和原 right 的后继。这种"反转一小段 + 接回原链"是 LC 92 和 LC 25 的共同骨架，把 LC 206 看成 left = 1, right = n 的特例即可。
"k 个一组反转"再加一层：先 peek 当前组是否有完整的 k 个节点（不够 k 个保持原样），够就反转，把反转结果拼回前一组的尾巴，再进入下一组。把"反转一段 + 接回原链"封装成子过程，所有变体都能套。
2. 通用模板
反转族的最小骨架抽出三件事——prev / cur / nxt 三个游标 + 四步赋值 + dummy 节点统一边界——剩下的题目逻辑往里填。下面给三个语言的核心模板：模板 A 反转整条链、模板 B 反转前 k 个节点（LC 25 子过程）、模板 C 头插法反转 [left, right] 段（LC 92 主路径）。
模板 A：反转整条链（三指针迭代）
def reverse_list(head):
"""反转单链表，返回新头节点。三指针迭代，O(n) 时间 / O(1) 空间。"""
prev, cur = None, head
while cur:
nxt = cur.next # ① 缓存原 next（必须在改 cur.next 之前）
cur.next = prev # ② 重定向到前驱
prev = cur # ③ 滑动 prev
cur = nxt # ④ 滑动 cur
return prev # cur 走到 null，prev 就是新头public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next; // ① 缓存原 next
cur.next = prev; // ② 重定向到前驱
prev = cur; // ③ 滑动 prev
cur = nxt; // ④ 滑动 cur
}
return prev;
}ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* nxt = cur->next; // ① 缓存原 next
cur->next = prev; // ② 重定向到前驱
prev = cur; // ③ 滑动 prev
cur = nxt; // ④ 滑动 cur
}
return prev; // cur 走到 null，prev 就是新头
}模板 B：反转链表中前 k 个节点
def reverse_k(head, k):
"""反转前 k 个节点，返回 (新头, 第 k+1 个节点)。"""
prev, cur = None, head
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev, cur # prev 是反转段新头，cur 是原链第 k+1 个// 返回 [反转段新头, 原链第 k+1 个节点]
ListNode[] reverseK(ListNode head, int k) {
ListNode prev = null, cur = head;
for (int i = 0; i < k; i++) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return new ListNode[]{prev, cur};
}// 返回 {反转段新头, 原链第 k+1 个节点}
std::pair<ListNode*, ListNode*> reverseK(ListNode* head, int k) {
ListNode *prev = nullptr, *cur = head;
for (int i = 0; i < k; i++) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return {prev, cur};
}模板 A 是模板 B 取 k = n（走到 cur 是 null）的特例。这个版本会作为 LC 25 的子过程。
模板 C：头插法反转 [left, right] 段
def reverse_between(head, left, right):
"""反转区间 [left, right]（1-indexed），返回新链头。"""
dummy = ListNode(0, head)
p_prev = dummy
for _ in range(left - 1): # p_prev 走到 left 的前一个
p_prev = p_prev.next
cur = p_prev.next # cur 是区间第一个（反转后变成区间尾）
for _ in range(right - left): # 头插 right - left 次
nxt = cur.next
cur.next = nxt.next # 把 nxt 从 cur 后面摘下
nxt.next = p_prev.next # 把 nxt 插到 p_prev 之后（成为新的区间头）
p_prev.next = nxt
return dummy.nextListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode pPrev = dummy;
for (int i = 0; i < left - 1; i++) {
pPrev = pPrev.next;
}
ListNode cur = pPrev.next;
for (int i = 0; i < right - left; i++) {
ListNode nxt = cur.next;
cur.next = nxt.next;
nxt.next = pPrev.next;
pPrev.next = nxt;
}
return dummy.next;
}ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* pPrev = &dummy;
for (int i = 0; i < left - 1; i++) {
pPrev = pPrev->next;
}
ListNode* cur = pPrev->next;
for (int i = 0; i < right - left; i++) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = pPrev->next;
pPrev->next = nxt;
}
return dummy.next;
}三个模板共享同一份骨架，区别只在"反转哪一段"和"反转后怎么接回原链"。几点要说明：
- 四步赋值顺序绝对不能换。
nxt = cur.next必须最先——cur.next还是原值时缓存下来，否则下一句改掉就丢了原后继。cur.next = prev必须在prev = cur之前——一旦prev = cur，prev 也变成 cur，再写cur.next = prev就是自环。 - 循环条件用
while cur而非while cur and cur.next。最后一个节点也需要做一次cur.next = prev（指向倒数第二个），漏掉它就丢一个反转操作。 prev初值的妙用：标准模板里prev = None表示反转段末尾接 null；分组反转时把prev初值设成"下一组的第一个节点"，反转过程就顺手把当前段尾巴接到下一段，省一行拼接（见 §4.3 LC 25）。- dummy 节点统一边界。
p_prev = dummy时p_prev.next永远是当前段第一个节点，不用为left == 1（反转包含头节点）单独写分支。头插法天然在循环里维护"反转段的头是p_prev.next"，结束时不需要额外拼接。
3. 母题精讲
LeetCode 206. Reverse Linked List
链接：LeetCode 206
题目（中文翻译）：给一个单链表的头节点 head，把整条链表的方向反过来——原来 1 → 2 → 3 → 4 → 5 变成 5 → 4 → 3 → 2 → 1，返回反转后链表的新头节点。
数据范围：
- 链表节点数：0 到 5000
- 节点值：−5000 到 5000
示例：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]
输入：head = [1, 2]
输出：[2, 1]
输入：head = []
输出：[]暴力解：递归把"反转后接上 head"翻成递推
直觉解是递归：假设 reverse(head.next) 已经把后面那段反转好，并返回反转后的新头 newHead。原链是 head → head.next → ...，反转后 head.next 那段已经倒过来，它的尾巴就是原来的 head.next。所以把 head 接到那段的尾巴后面：让 head.next.next = head，再把 head.next 切成 null（否则它会和原 next 形成环）。
class Solution:
def reverseList_recursive(self, head: 'ListNode') -> 'ListNode':
if head is None or head.next is None: # 空链表或单节点：直接返
return head
new_head = self.reverseList_recursive(head.next)
head.next.next = head # 把原 head 接到反转段的尾巴
head.next = None # 切断原 next，防止成环
return new_headpublic ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}ListNode* reverseListRecursive(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}时间 O(n)、空间 O(n)——递归栈深度等于链表长度。LC 206 数据范围 5000 撑得住，但工程里链表可能上百万节点，Python 默认递归深度 1000、Java 栈深度受 -Xss 限制，长链直接 stack overflow。目标是 O(n) 时间 + O(1) 额外空间的迭代解——模板 A 即标准答案。
三指针迭代的步进可视化
走一遍 1 → 2 → 3 → 4 → 5。把节点平铺成数组展示，红色表示 prev、金色表示 cur、蓝色表示已反转完毕、灰色是 next（还没动）：
reverseList: 1 → 2 → 3 → 4 → 5
三指针迭代：prev/cur/next，每轮把 cur.next 重定向到 prev
每轮三个指针滑动一格，新建一根 next 指针。整个过程没开数组、没递归——只用 prev / cur / nxt 三个变量。这就是 LC 206 的标准答案，§4.1 给完整代码。
4. 例题（三道）
下面三道题按"反转范围递增"排：整条链 → 一个区间 → 每 k 个一组。每道末尾给一个 follow-up 直接续到下一题。
4.1 LC 206 反转链表
链接：LeetCode 206
题意：给单链表头节点 head，反转整条链表，返回反转后的新头节点。要求 O(n) 时间，并尽量做到 O(1) 额外空间。
数据范围：
- 链表节点数：0 到 5000
- 节点值：−5000 到 5000
示例：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]
输入：head = [1, 2]
输出：[2, 1]
输入：head = []
输出：[]直接套模板 A：
class Solution:
def reverseList(self, head: 'ListNode') -> 'ListNode':
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prevpublic class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
}class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
};几个细节值得讲：
第一，四条赋值的顺序绝对不能换。nxt = cur.next 必须最先——cur.next 还是原值时缓存下来，否则下一句 cur.next = prev 改掉之后就丢了原来的后继。cur.next = prev 必须在 prev = cur 之前——一旦 prev = cur，prev 也变成 cur，再写 cur.next = prev 就成了"指向自己"形成自环。
第二，为什么循环条件是 while cur，不是 while cur and cur.next？因为最后一个节点 cur 也需要做一次 cur.next = prev（指向倒数第二个）。如果用 while cur and cur.next，最后一个节点的 next 还是原来的 null——刚好碰巧对，但中间任何一个节点漏处理就会出错。规则是"只要 cur 还在就继续处理它"。
第三，返回 prev 而不是 cur。循环退出时 cur is null，prev 是原链的最后一个节点——也就是反转后链表的头。
第四，空链表自然过：head is null 时，初始 cur = null，循环不进，直接返回 prev = null。单节点链表同理：循环跑一轮，cur.next = null（prev 初始就是 null），返回 prev = head。
复杂度：时间 O(n)，空间 O(1)。每个节点访问 1 次，重定向 1 次。
Follow-up：反转整条链是最简单的情况。如果题目只让你反转某个区间 [left, right]——前后两段保持原样，只翻中间一段呢？
4.2 LC 92 反转链表 II
链接：LeetCode 92
题意：给单链表头节点 head 和两个整数 left、right（满足 1 ≤ left ≤ right ≤ n），反转下标 [left, right] 之间的节点（1-indexed），返回反转后的链表头。要求一次遍历。
数据范围：
- 链表节点数：1 到 500
- 节点值：−500 到 500
1 ≤ left ≤ right ≤ n
示例：
输入：head = [1, 2, 3, 4, 5], left = 2, right = 4
输出：[1, 4, 3, 2, 5]
解释：反转区间 [2, 4]，原链中下标 2~4 的值是 2、3、4，翻转后变成 4、3、2。
输入：head = [5], left = 1, right = 1
输出：[5]这道题用模板 C 的头插法最干净。核心思路：
- 用 dummy 节点统一边界（避免
left = 1时新头变化的特殊处理）。 - 让
p_prev走到 left 的前一个节点。 - 把 left 之后的
right - left个节点，逐个"头插"到p_prev之后。
class Solution:
def reverseBetween(self, head: 'ListNode', left: int, right: int) -> 'ListNode':
dummy = ListNode(0, head)
p_prev = dummy
for _ in range(left - 1): # 走到 left 的前驱
p_prev = p_prev.next
cur = p_prev.next # 区间第一个（反转后变成区间尾）
for _ in range(right - left): # 头插 right - left 次
nxt = cur.next # 待头插的节点
cur.next = nxt.next # 把 nxt 从原位置摘下
nxt.next = p_prev.next # 把 nxt 插到 p_prev 之后（成为新的区间头）
p_prev.next = nxt
return dummy.nextpublic class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode pPrev = dummy;
for (int i = 0; i < left - 1; i++) {
pPrev = pPrev.next;
}
ListNode cur = pPrev.next;
for (int i = 0; i < right - left; i++) {
ListNode nxt = cur.next;
cur.next = nxt.next;
nxt.next = pPrev.next;
pPrev.next = nxt;
}
return dummy.next;
}
}class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* pPrev = &dummy;
for (int i = 0; i < left - 1; i++) {
pPrev = pPrev->next;
}
ListNode* cur = pPrev->next;
for (int i = 0; i < right - left; i++) {
ListNode* nxt = cur->next;
cur->next = nxt->next;
nxt->next = pPrev->next;
pPrev->next = nxt;
}
return dummy.next;
}
};头插法的几何直觉：用 [1, 2, 3, 4, 5]、left = 2, right = 4 走一遍。
初始：dummy → 1 → 2 → 3 → 4 → 5
↑p_prev ↑cur
轮 1 头插（把 3 摘下来插到 p_prev 之后）：
dummy → 1 → 3 → 2 → 4 → 5
↑p_prev ↑cur（cur 没变，还是 2，但 2.next 已经从 3 变成 4）
轮 2 头插（把 4 摘下来插到 p_prev 之后）：
dummy → 1 → 4 → 3 → 2 → 5
↑p_prev ↑cur（cur 还是 2，2.next 现在是 5）
right - left = 4 - 2 = 2 轮做完，退出。返回 dummy.next = 1。注意 cur 一直是原链的 left 节点（这里是 2），它在反转过程中位置在动但引用没变——每轮都把它的下一个摘下来插到前面。cur.next 不断在变（2 → 4 → 5），所以 cur 最终自动落到反转段的尾巴位置，接上原来 right 的后继。
为什么用头插法不用三指针迭代？两种都能做。三指针迭代版的代码会长一些：
# 三指针迭代版（备选）
p_prev = dummy
for _ in range(left - 1):
p_prev = p_prev.next
left_node = p_prev.next # 反转后这个节点变成区间尾
prev, cur = None, left_node
for _ in range(right - left + 1):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
left_node.next = cur # 区间尾接上原 right 的后继
p_prev.next = prev # p_prev 接上区间新头它需要在反转结束后显式拼接两个断点（left_node.next = cur 和 p_prev.next = prev），头插法因为每轮都在维护"反转段的头是 p_prev.next"，自然就接好了。代码短 4 行。
边界踩坑：
第一，left == right 时区间长度为 1，不用反转。代码里 for _ in range(right - left) 直接是 range(0)，循环不进，dummy.next 还是原 head，正确。
第二，left == 1 时反转包含头节点。dummy 的作用就是把"反转头节点"统一成"反转 dummy 后面的某段"——p_prev = dummy 时一切照旧。
第三，right == n 时反转到末尾。cur.next = nxt.next 中 nxt.next 是原 right 的后继，可能是 null——cur.next = null 也没问题（最后一轮把 right 接到 p_prev 之后，cur 自然落在末尾）。
复杂度：时间 O(n)（走到 left 用 O(left)，反转用 O(right - left)），空间 O(1)。"一次遍历"达成。
Follow-up：反转一个区间已经有点意思了。如果题目把链表按 k 个一组分块，每一组都要反转，最后不足 k 个的保持原样呢？
4.3 LC 25 K 个一组翻转链表
链接：LeetCode 25
题意：给链表头节点 head 和正整数 k，把链表按每 k 个节点一组进行翻转，返回翻转后的链表。如果末尾剩余节点数 < k，保持原顺序不翻转。算法用 O(1) 额外空间。
数据范围：
- 链表节点数：1 到 5000
- 节点值：0 到 1000
1 ≤ k ≤ 链表节点数
示例：
输入：head = [1, 2, 3, 4, 5], k = 2
输出：[2, 1, 4, 3, 5]
解释：前 2 个翻转成 [2, 1]，下两个翻转成 [4, 3]，剩 1 个不动 [5]。
输入：head = [1, 2, 3, 4, 5], k = 3
输出：[3, 2, 1, 4, 5]
解释：前 3 个翻转成 [3, 2, 1]，剩 2 个不足 3 不动 [4, 5]。
输入：head = [1, 2, 3, 4, 5], k = 1
输出：[1, 2, 3, 4, 5]这是反转族的"集大成"题——核心思路：先 peek 一组是否完整（数出 k 个节点），完整就反转这一组，并把反转结果拼回前一组的尾巴。
骨架：
- 用 dummy 节点。
group_prev指向"上一组反转后的尾巴"（也就是当前组的前驱），初始为 dummy。 - 循环：从
group_prev.next出发，往后走 k 步看是否能数满。够 → 反转这一组；不够 → 退出。 - 反转后的新头接到
group_prev.next，反转后的尾巴接到下一组的头。然后group_prev滑到当前组的尾巴，进入下一轮。
class Solution:
def reverseKGroup(self, head: 'ListNode', k: int) -> 'ListNode':
dummy = ListNode(0, head)
group_prev = dummy # 当前组的前驱
while True:
# 1. peek 是否有完整的 k 个：让 kth 走到当前组的最后一个节点
kth = group_prev
for _ in range(k):
kth = kth.next
if kth is None: # 不足 k 个，结束
return dummy.next
group_next = kth.next # 下一组的第一个节点（反转前要缓存）
# 2. 反转当前组（从 group_prev.next 开始的 k 个节点）
prev, cur = group_next, group_prev.next
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
# 3. 拼接：原来 group_prev → 当前组头，现在 group_prev → kth（当前组反转后的新头）
tmp = group_prev.next # tmp 是当前组反转前的头 = 反转后的尾
group_prev.next = kth # 接上反转后的新头
group_prev = tmp # 滑到下一组的前驱public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth.next;
if (kth == null) return dummy.next;
}
ListNode groupNext = kth.next;
ListNode prev = groupNext, cur = groupPrev.next;
for (int i = 0; i < k; i++) {
ListNode nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
ListNode tmp = groupPrev.next;
groupPrev.next = kth;
groupPrev = tmp;
}
}
}class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
// 1. peek 是否有完整的 k 个：让 kth 走到当前组的最后一个节点
ListNode* kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth->next;
if (kth == nullptr) return dummy.next; // 不足 k 个，结束
}
ListNode* groupNext = kth->next; // 下一组的第一个（反转前要缓存）
// 2. 反转当前组：prev 初始为 groupNext，顺手把当前组尾巴接到下一组
ListNode* prev = groupNext;
ListNode* cur = groupPrev->next;
for (int i = 0; i < k; i++) {
ListNode* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
// 3. 拼接：原 groupPrev → 当前组头，现在 groupPrev → kth（反转后的新头）
ListNode* tmp = groupPrev->next; // 反转前的头 = 反转后的尾
groupPrev->next = kth;
groupPrev = tmp; // 滑到下一组的前驱
}
}
};反转 k 个节点这一步的小 trick：注意 prev 的初值不是 null 而是 group_next（下一组的第一个节点）。为什么？因为当前组反转完后，它的尾巴（原来的头）需要指向下一组的第一个。如果用 prev = null 反转 k 步，反转后的尾巴 next 是 null——还要额外一行拼接。直接把 prev 初始化为 group_next，反转过程顺手把当前组的尾巴接到下一组，省一行。
走一遍 [1, 2, 3, 4, 5], k = 2：
初始：dummy → 1 → 2 → 3 → 4 → 5 → null
↑group_prev
轮 1：
- kth 走 2 步到节点 2，group_next = 3
- 反转 [1, 2]：prev 初始为 3。反转后 prev = 2, 1.next = 3（顺手接上下一组）
现在链表："孤立" 2 → 1 → 3 → 4 → 5（注意此时 dummy.next 还是 1，没断）
- tmp = group_prev.next = 1（反转前的头 = 反转后的尾）
- group_prev.next = kth = 2 → dummy → 2 → 1 → 3 → 4 → 5
- group_prev = tmp = 1（节点 1，下一组的前驱）
轮 2：
- kth 走 2 步从节点 1 出发到节点 4，group_next = 5
- 反转 [3, 4]：prev 初始为 5。反转后 prev = 4, 3.next = 5
- tmp = group_prev.next = 3
- group_prev.next = kth = 4 → dummy → 2 → 1 → 4 → 3 → 5
- group_prev = 3
轮 3：
- kth 从 3 走 2 步：3 → 5 → null，第 2 步 kth = null，return dummy.next
最终：2 → 1 → 4 → 3 → 5为什么不用递归更短？递归版确实更短：
def reverseKGroup_recursive(head, k):
# peek 是否有 k 个
cur = head
for _ in range(k):
if cur is None:
return head # 不足 k 个，整段不动
cur = cur.next
# 反转前 k 个
prev, cur = self.reverseKGroup_recursive(cur, k), head # 递归先处理后面
for _ in range(k):
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev递归版只有 10 行，但栈深度是 O(n/k)——n 是 5000、k 是 1 的最坏情况下深 5000，Python 默认递归 1000 直接 RecursionError。LC 25 的"O(1) 额外空间"要求迭代实现。
边界：
第一，k == 1 时不反转。迭代版本：反转循环跑 1 次相当于"把当前节点的 next 设为下一组的第一个"——结果和不反转一样。
第二，链表长度恰好是 k 的倍数时。最后一组反转完，下一轮 kth 从 group_prev 走 k 步，第 k 步 kth = null，return。
第三，整条链不足 k 个。第一轮 kth 还没走完就成了 null，直接 return dummy.next，原链未动。
复杂度：时间 O(n)——每个节点访问常数次（peek 一次 + 反转一次）。空间 O(1)。
这三道题共享同一份代码骨架：三指针滑动 + 局部 next 重定向 + 用 dummy 统一拼接边界。LC 206 是整条链反转、LC 92 是一个区间反转、LC 25 是把链表切成多个区间逐个反转。把反转封装成"反转 k 个节点 + 拼回前后"的子过程，所有变体都能套。
LC 25 常见 follow-up：
- "如果
k > n是否要反转剩余段？" → 题面默认不反，但有变体要求反；面试现场先问清楚再写。 - "能否原地（O(1) 空间）+ 不修改
next指针顺序？" → 不行，链表反转的本质就是改 next。除非允许新建节点。
反转作为子过程：在哪些题里复用？
反转链表很少作为终极题考——它更常作为组合题的一个子过程：
| 题号 | 主题 | 反转扮演的角色 |
|---|---|---|
| LC 234 | 回文链表 | 快慢指针定中点，反转后半段，与前半段逐节点比 |
| LC 143 | 重排链表 | 找中点 → 反转后半段 → 两段交错合并 |
| LC 2130 | 链表中相邻节点最大孪生和 | 找中点 → 反转后半段 → 双指针比每对孪生 |
| LC 61 | 旋转链表 | 闭环 + 在新尾巴处断开（不是反转，但同一族指针操作） |
这些题里反转都是O(1) 空间的"原地操作"——题目要求不允许复制成数组再翻转，必须用三指针迭代。把反转封装成 reverse(head: Optional[ListNode]) -> Optional[ListNode] 一个工具函数，后续这些题直接调即可。
与快慢指针的关系：反转和快慢指针几乎总是搭档出现——快慢指针定位中点 / 环入口，反转处理"后半段需要倒着看"的需求。LC 234 / LC 143 / LC 2130 都是这套模式。
5. 边界、易错与复杂度
三指针赋值顺序
四条赋值的标准顺序是：
nxt = cur.next # ① 缓存
cur.next = prev # ② 重定向
prev = cur # ③ 滑动 prev
cur = nxt # ④ 滑动 cur任何打乱都会出错：
| 错位 | 后果 |
|---|---|
| 把 ① 放到 ② 之后 | cur.next 已被改成 prev，丢失原后继 |
| 把 ② 放到 ③ 之后 | prev = cur 后 prev 也是 cur，cur.next = prev 成自环 |
| 把 ④ 放到 ③ 之前 | cur = nxt 后 prev = cur 错位 |
记法：先存后改先滑 prev 再滑 cur——nxt 是临时变量必须先存，prev 比 cur 滞后一格所以先滑 prev。
dummy 节点的两个用处
第一，统一"反转头节点"的边界。LC 92 / LC 25 里反转区间可能包含原 head，dummy.next 一开始指向 head，反转后 dummy.next 自动就是新头，免去 if left == 1 的特殊处理。
第二，统一"前驱为 null"的边界。group_prev = dummy 时，group_prev.next 就是当前组的第一个节点，赋值操作完全统一。
什么时候不用 dummy？LC 206 不需要——它返回的是 prev，循环开始时 prev 直接是 null 就够。但凡涉及"区间反转 + 拼接回原链"，dummy 都能省 4~6 行边界代码。
空链表 / 单节点 / k = 1
模板对这些边界都自洽：
- 空链表：LC 206 直接
while cur不进，返回prev = null。LC 92 / LC 25 数据范围保证链表非空。 - 单节点：LC 206 跑一轮，
cur.next = null（prev 初始 null），返回原节点。LC 92left = right = 1时反转循环不进。LC 25k = 1等价不反转。 right - left = 0：LC 92 反转长度为 1 的区间，循环不进，区间保持原样。
自环风险
写反转时一个经典 bug 是漏写 head.next = null 导致自环（出现在递归版）。考虑 head = [1, 2]：
def buggy(head):
if head is None or head.next is None:
return head
new_head = buggy(head.next)
head.next.next = head
# 漏写 head.next = None
return new_head走完后 2 → 1，但 1.next 还是 2（递归前的原值没动），形成 1 → 2 → 1 → 2 → ... 自环。所以递归版必须显式 head.next = None。迭代版不会有这个问题——cur.next = prev 会覆盖原值。
反转后的"接缝"
LC 92 / LC 25 里反转完一段后，要把反转段重新接回原链，涉及两个接缝：
- 接缝 1：原链 left 的前驱 → 反转后的新头（也就是原 right 节点）。代码里是
p_prev.next = kth或p_prev.next = prev。 - 接缝 2：反转后的新尾（也就是原 left 节点）→ 原 right 的后继。代码里是
left_node.next = group_next或在三指针反转时把prev初值设成group_next顺手接上。
漏接接缝 2 会导致反转段后面"断流"——原链 right 之后的节点全部丢失。漏接接缝 1 会让反转段"游离"，dummy.next 还是原头。
调试时如果输出比预期短，几乎可以确定是接缝 2 丢了。
复杂度速查
| 操作 | 时间 | 空间 |
|---|---|---|
| LC 206 反转整条链（迭代） | O(n) | O(1) |
| LC 206 反转整条链（递归） | O(n) | O(n)（栈） |
| LC 92 反转区间 [left, right] | O(n) | O(1) |
| LC 25 k 个一组反转 | O(n) | O(1) |
n 是链表节点数。LC 25 虽然外层有 n/k 轮、每轮 peek 走 k 步 + 反转 k 步，总操作仍是 2n = O(n)。
7. 小结
反转族的核心是"三指针滑动 + 局部 next 重定向"——每一步只修改一根指针，靠 prev / cur / nxt 三个游标维护"前驱、当前、后继"的一手信息。LC 206 是整条链的反转、LC 92 把它压到一个区间、LC 25 切成多个区间逐个反转。配合 dummy 节点统一拼接边界，空间永远是 O(1)，时间 O(n)。
下一节会把"链表 + 双指针"的范围扩到合并、排序与去重——LC 21 / 23 / 148 这一族题需要把多条链揉成一条。
对应灵神题单：链表 / 反转 / k 个一组
进一步阅读：灵茶山艾府《链表题单》；LeetCode 链表标签