本算法采用双指针迭代法解决“单链表反转”问题。其核心本质是在单次线性扫描中利用局部临时变量暂存后继节点原地改变当前节点的指针指向从而将额外空间复杂度控制在常数阶 O(1)。该解法是链表逆序操作的最优原地解法最终走向是通过指针的交替推进直接输出反转后的新链表头节点。一、 问题本质与数据模型对于给定的单链表其物理结构是由一系列在内存中分散分布的节点ListNode通过指针单向连接而成。每个节点包含一个存储数据的变量val和一个指向下一个节点的指针next。设链表的初始物理状态拓扑结构为head - 1 - 2 - 3 - 4 - 5 - null反转链表的目标是改变每个节点内部next指针的指向使其指向其前驱节点最终构建出如下拓扑结构null - 1 - 2 - 3 - 4 - 5 (new_head)在处理该逆序转换时算法面临一个关键的物理约束一旦将当前节点cur的next指针强行指向其前驱节点pre即执行cur.next pre当前节点与原有后继节点之间的物理连接就会立即断开。为了防止后续节点在内存中丢失算法必须在修改指针指向之前引入一个临时局部变量nxt来暂存当前节点的原后继节点地址。二、 算法演进对比在解决单链表逆序变换问题时双指针迭代法在时空资源调配上达到了最优状态解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷栈/辅助数组法O(n)O(n)将所有链表节点顺次压入栈中随后利用栈的后进先出特性重新串联节点引入了与链表长度等长的额外内存开销非原地解法递归解法O(n)O(n)递归层层深入到链表尾部在回溯过程中改变相邻节点的指针指向递归调用会产生与链表长度正比的系统栈帧消耗面临大样本下的栈溢出风险双指针迭代法当前解法O(n)O(1)利用两个物理指针同向交替推进在单次遍历中原地修改指针指向需要在每次迭代中严密维护三个局部变量的赋值顺序三、 核心控制逻辑拆解当前源码通过一个while (cur ! null)循环体实现了无额外空间的就地指针反转。其核心运行逻辑包含以下四个串行步骤1. 后继节点缓存ListNode nxt cur.next;作用将当前节点原本的下一个节点地址保存到nxt中确保后续遍历链表的通路不会中断。2. 指针方向逆转cur.next pre;作用切断当前节点向后的指针使其转向前推指向已经处理过的前驱节点pre。1. 前驱指针推进pre cur;作用前驱指针pre向右移动占领当前cur的位置为下一个节点的反转做准备。4. 当前指针推进cur nxt;作用当前指针cur步进到先前缓存的nxt位置使控制流进入下一次迭代。四、 算法执行状态机步进示例以输入数据head [1, 2, 3]为例初始化pre nullcur 1。代码在循环内部的状态演进过程如下表所示迭代步数状态阶段cur指针位置pre指针位置nxt暂存位置链表内部实时拓扑状态初始循环前指向 1null未定义1 - 2 - 3 - null第 1 步循环中指向 1null指向 2执行反转后null - 1此时 2 和 3 独立连接第 1 步结束赋值后指向 2指向 1指向 2指针更替完成pre位于 1cur位于 2第 2 步循环中指向 2指向 1指向 3执行反转后null - 1 - 2第 2 步结束赋值后指向 3指向 2指向 3指针更替完成pre位于 2cur位于 3第 3 步循环中指向 3指向 2null执行反转后null - 1 - 2 - 3第 3 步结束赋值后null指向 3null指针更替完成pre位于 3cur变为null终止循环后null指向 3-cur null循环破裂返回pre即新链表头 3五、源码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseList(ListNode head) { // 动态维护当前正在处理的节点 ListNode cur head; // 动态维护当前节点的前驱节点初始时头节点的前驱为 null ListNode pre null; // 当 cur 为 null 时说明整条链表已遍历并反转完毕 while (cur ! null) { // 步骤 1临时斩断并缓存当前节点的后继节点防止链表断裂丢失 ListNode nxt cur.next; // 步骤 2核心反转动作将当前节点的指针指向其前方的前驱节点 cur.next pre; // 步骤 3前驱指针 pre 向后移动一步更新为当前节点 pre cur; // 步骤 4当前指针 cur 向后移动一步前进到原链表的下一个位置 cur nxt; } // 当循环退出时cur 指向 null而 pre 恰好指向原链表的最后一个节点即新链表的头节点 return pre; } }六、 复杂度极限分析1. 时间复杂度O(n)分析算法引入的cur指针从链表头节点出发通过cur nxt的指令逐位向后步进直至到达链表末尾的null。在整个执行周期中链表中的每个节点均被精确访问且仅访问了一次。结论总基本指令的执行次数与链表节点的总数 n 呈严格的线性正比关系。2. 空间复杂度O(1)分析该算法的所有指针反转与改写逻辑全部在传入的原链表物理节点内存块上展开原地算法。运行期间除独立声明了cur、pre、nxt三个用于控制迭代及辅助对调的引用类型局部变量外没有申请任何外部辅助数组或动态拓扑结构。结论程序运行分配的内存空间完全固定不随输入数据规模 n 的扩大而产生任何增长空间消耗保持为常数阶。