反转链表只需改一条边，为什么递归版会先把栈撑爆
链表反转要做的事其实只有一件：把每个节点的 next 从指向后继改成指向前驱。三种常见写法——迭代三指针、递归、哑节点头插——时间复杂度都是 O(n)，差别全在改指针的时机和额外空间。迭代用两个变量滚动，空间 O(1)；递归把"记住后继"这件事交给调用栈，代码短却要压 n 层栈帧，长链表上会栈溢出；头插法靠哨兵把节点逐个摘下来挂到新链头。最常见的坑是赋值顺序写反导致自环，以及反转区间后忘了把原头节点的 next 置空。读完你能说清三种写法各自在改哪条边、边界怎么处理，以及面试现场该选哪一种。
是什么
单链表的每个节点只保存一个指向后继的 next 指针，整条链的方向由这些指针串起来。所谓反转，就是把每一条 next 边的方向调头：原来的头变成尾，原来的尾变成头，节点本身一个都不移动、不复制。一句话直觉：这像一列挂钩全部朝后的火车，调头就是把每节车厢的挂钩改成朝前——但在改之前，你必须先记住后面那节车厢是谁，否则一松手整列就脱钩了。
它是面试里出现频率最高的链表题，也是很多真实逻辑的地基：判断回文链表要反转后半段，两数相加要从低位开始算，撤销栈和浏览历史的前进后退，本质都是在一条链上换方向。题面越短，越能看出一个人对指针、边界和空间的敏感度。
值得先分清的是它和数组反转的差别。数组反转交换的是两个位置上的值，元素在内存里的位置不变，靠下标就能随机访问；链表没有下标，想碰到第 n 个节点只能从头一路 next 走过去。所以数组反转是"就地换值"，链表反转是"就地改边"，前者拼的是循环怎么写，后者拼的是你有没有在改边之前把后路留好。这也解释了为什么链表题的错误几乎都发生在指针赋值的那一行，而不是在循环条件上。
核心原理
三种写法解的都是同一道方程，区别只在于"谁负责记住后继"。
迭代三指针：维护 prev（已反转段的头）、cur（未反转段的头）。每一轮先把 cur.next 存进临时变量 nxt，再让 cur.next 指向 prev，最后把 prev 和 cur 各向前挪一格。循环不变量很清晰：prev 左边的部分已经全部调头，cur 及其右边还没动。走完时 cur 为空，prev 停在原尾节点上，它就是新头。
递归：把"反转 head 之后的整条链"托付给下一层调用，拿到返回的新头后再收拾自己这一层。它从最后一个节点开始往回挂，所以也叫尾插法；而迭代在前进过程中就把当前节点挂到已反转段的前面，本质是就地头插。
哑节点头插：先造一个 dummy，把原链的第一个节点接在它后面，然后反复取下 dummy 后面的下一个节点，插到 dummy 正后方。它的价值不在反转整条链——那和迭代等价——而在于反转前 k 个或某个区间时，哨兵把"从第一个节点就开始反"这种边界抹平了。
def reverse_iter(head):
prev, cur = None, head
while cur:
nxt = cur.next # 先存后继，否则改完就再也找不到
cur.next = prev # 调头
prev, cur = cur, nxt
return prev # prev 落在原尾，即新头
def reverse_rec(head):
if head is None or head.next is None:
return head
new_head = reverse_rec(head.next)
head.next.next = head # 让后一个节点指回来
head.next = None # 再断开自己；这两行顺序反了会自环
return new_head两段代码各有一个不能错的细节。迭代里那句 nxt = cur.next 必须放在改指针之前：一旦 cur.next = prev 执行完，通往剩余链表的唯一入口就被覆盖了，后面的节点既找不到也回收不掉。递归里两个赋值同样有严格顺序：先建立回边 head.next.next = head，再断开旧边 head.next = None；如果先置空，head.next 已经是 None，再去取它的 next 就会直接抛异常。
哑节点头插常被当成第四种写法，其实它和迭代同源：都是把当前节点从原链上摘下来、挂到已反转段的头部，只不过一个用 prev 当活动的头，一个用固定的 dummy 当锚点。理解了这一点，K 个一组反转就不再是新题——外层循环每轮数出 k 个节点，记下这一组的后继，内层把这 k 个节点按头插或三指针翻完，再把上一组的尾巴、这一组的新头、下一组的头三处接回去。所有链表反转的变体，拆开看都是"反转一段 + 接三根线"。
空间上的分水岭也在这里。迭代只用了三个指针变量，是 O(1) 额外空间；递归没有显式开数组，但每一层调用都要在调用栈上留一个栈帧，深度等于链表长度，所以是 O(n) 空间。这不是"理论上"的差别：Java 线程栈默认通常只有 512 KB 到 1 MB（随平台和启动参数变化），Python 默认递归深度上限是 1000 层，十万个节点的链表用递归反转，等不到返回就会栈溢出。Go 的 goroutine 栈可以动态增长，深递归不至于立刻崩，但那份 O(n) 的内存账单照付。
常见考点与误区
- 误区一："递归写法更优雅，空间也是 O(1)"：错。递归的空间成本被隐藏在调用栈里，深度就是链表长度。面试官追问"十万节点会怎样"，答"会栈溢出"才是及格线，能补一句各语言栈的实际限制更好。
- 误区二：先断开再回指：把
head.next = None写在head.next.next = head前面，第二句等于对一个 None 取属性，直接空指针异常。这两行的顺序是这类题最高频的翻车点。 - 误区三：忘记把原头的 next 置空：整条链反转完，原头成了尾，如果它的 next 还指着第二个节点，链表就首尾相连成环，任何遍历都会死循环。反转区间时更隐蔽——尾节点必须接上区间后的 succ，否则链断成两截。
- 考点四：返回值到底是谁：迭代版返回 prev 而不是 cur（循环结束时 cur 已是 None）；递归版必须把最底层返回的 new_head 一路原样透传，不能返回当前 head，否则拿到的只是反转后的尾巴。
- 考点五：边界与哨兵：空链表、单节点、只反转前 k 个、left 等于 1 的区间反转，都是同一类边界。哑节点不是花活，它让"区间前驱"永远存在，省掉一堆 if。
- 考点六：能不能靠复制值实现：不能。反转改的是边的方向，节点身份不变；如果节点还被别的结构引用，复制值会让两处视图不一致。
- 考点七：K 个一组反转的收尾：不足 k 个的那一组要保持原样，这意味着你必须先数够 k 个再动手；数不够就直接返回，不能反转一半。同时上一组的尾、本组的新头、下一组的头三根线一根都不能漏，漏一根就是断链或成环。
实践建议
- 生产代码优先选迭代：O(1) 空间、无栈风险、异常路径也好推理。递归留给深度可控（比如千级以内）或纯教学场景。
- 涉及区间反转一律先上哑节点，把 pre、newHead、succ 三个位置在纸上标出来，再动手写拼接，能避免绝大多数断链和成环。
- 写完别急着提交，拿三个节点手跑一遍，再用"遍历计数是否等于原长度"或 Floyd 判环做一次自检；成环问题靠肉眼很难发现。
- 反转是就地修改，不是原子操作。若有其他线程或读者正在遍历同一条链，会看到半反转甚至带环的中间态，必须加锁、用 RCU，或者改成写时复制的新链。
- 语言细节值得记：固定栈的运行时（Java、C++ 常见配置）深递归更早崩，栈可增长的运行时只是把崩溃点往后推，空间复杂度并不会因此变好。
一句话总结：三种写法时间都是 O(n)，真正的分水岭是谁替你记住后继——迭代用两个变量，递归用 n 层栈帧。