反转链表

可以遍历把值压进数组/栈，再倒着 new 一条新链表——但要 O(n) 额外空间，还白白新建了节点。更优雅的是原地：只改指针指向，O(1) 空间。

prev 跟在后面(初始 null)、cur 是当前节点。每一轮都做四个动作：①用 next 记住下一个(防断链)；② 把 cur.next 掉头指向 prev(原来的箭头先断开、再接到 prev)；③ prev 前进一步；④ cur 前进一步。cur 走到 null 时，prev 就是新头。下面一帧一个动作慢放。

起点 · prev=null, cur=头：cur 指向头节点 1，prev 此刻是 null(空)。准备把箭头一根根掉头。

① 记住 next = 2：动手前先用 next 抓住 2。一旦把 1 的箭头改了，就再也找不到后面——「先记 next」是不断链的命根子。

② cur.next 掉头 → prev(null)：执行 cur.next = prev：1 原来指向 2 的箭头先断开(图上变成 ·)，改指向 prev=null。还好 next 仍抓着 2，没丢。

③④ prev、cur 各前进一步：prev 来到刚处理完的 1、cur 来到 2。第一轮四步走完，1 已经「翻好」(它的箭头朝向 null)。

① 记住 next = 3：第二轮，同样先用 next 记住 3。

② cur.next 掉头 → prev(1)：cur.next = prev：2 原来指向 3 的箭头断开(右边变 ·)，改指向 prev=1——于是 2 → 1(左边箭头变 ←)。next 仍抓着 3。

③④ prev、cur 各前进：prev 前进到 2、cur 前进到 3。第二根也翻好了。

① 记住 next = null：第三轮，cur 现在是 3。记 next = cur.next，发现 3 后面是 null——说明 3 是原来的最后一个节点，这会是最后一轮。

② cur.next 掉头 → prev(2)：cur.next = prev：3 改指向 prev=2，3 → 2(右边箭头变 ←)。三根箭头现在全部掉头完毕。

③④ 完成 · cur=null, prev=新头：prev 前进到 3、cur 前进到 null，循环结束。此刻 prev 停在 3——它就是反转后的新头：3 → 2 → 1 → null。

链表操作的通用心法：改指针前，先用临时变量抓住会丢失的那一端。反转、删除、合并都靠它，绝不能让链断在手里。

雷区实演 · 若先掉头再读 next：假设第二轮忘了先存 next，直接执行 cur.next = prev：cur(2)的箭头当场掉头指回 1(左边变 ←)。此刻 2 原本通往 3 的那根线已经被覆盖了。

雷区实演 · 再去读 cur.next 拿到 prev：现在才想起去 nxt = cur.next 抓后面——可 cur.next 已经被改成 prev=1 了！读到的是 1 不是 3。节点 3(以及它后面的整段)彻底失联，再也回不去(图上 3 灰掉)。这就是「改指针前没先抓住后面」的真实灾难——所以铁律是先存 next，再掉头。

边界三连：反转链表 的边界先看最小规模、特殊输入和最容易触发分支的样例。

这套三指针是所有「局部反转」题的原子操作：LC92 只反转第 m~n 段（先走到 m，再套同样的翻转），LC25 每 K 个一组翻（翻完把段接回去）。学会这一道，链表反转一整类都通了——更多在 链表专题 继续。

面试追问：反转链表 的追问重点：递归与迭代的空间取舍、带环陷阱、以及换成双向链表时思路怎么变——把动画里的机制讲成自己的话。下一帧给出递归完整代码。