前端进阶之旅前端进阶之旅
  • 基础篇HTML/CSS/JS 打底
  • 进阶篇原理与工程化
  • 高频篇面试最常问的那批
  • 精选篇按模块收敛的总结
  • 手写篇常考代码手写实现
  • 面经篇真实面试问题复盘
  • AI 篇NEWAI 时代的前端考点
  • 历年面经NEW按年份追踪真实考点
  • 每日一题每天一道,攒手感
  • 专项自测100 题快速查漏
  • 小程序题库小程序专项刷题
  • 算法题库NEW在线编码即时判题
  • 知识卡片NEW碎片时间过考点
  • 面试题大全常见问题解析
  • AI 答疑NEW随时提问,即时解析
  • AI 模拟面试NEW模拟真实面试 + 报告
  • AI 定制路线NEW按你的简历现排
  • AI 知识地图NEW串起全站知识点
  • 原理篇React / Vue 源码拆解
  • HTTP从报文一路讲到 HTTPS
  • 浏览器渲染、事件循环、进程
  • 计算机基础Linux、网络、操作系统
  • 设计模式23 种模式怎么用
  • Node学习指南从环境搭建到服务端
  • NPM工作流script、依赖与发布
  • Docker容器化部署上手
  • Canvas图形与动画实战
  • 前端系统进阶学习大型项目工程化
  • 前端综合文章长期沉淀的实践文
  • 思维导图知识点全景图
  • 学习路线按图索骥不跑偏
  • AI 热点NEWAI 每日动态
  • 公众号动态公众号历史文章
  • 博客动态站长的技术博客
  • 开发者导航常用工具与文档站
  • 基础篇HTML/CSS/JS 打底
  • 进阶篇原理与工程化
  • 高频篇面试最常问的那批
  • 精选篇按模块收敛的总结
  • 手写篇常考代码手写实现
  • 面经篇真实面试问题复盘
  • AI 篇NEWAI 时代的前端考点
  • 历年面经NEW按年份追踪真实考点
  • 每日一题每天一道,攒手感
  • 专项自测100 题快速查漏
  • 小程序题库小程序专项刷题
  • 算法题库NEW在线编码即时判题
  • 知识卡片NEW碎片时间过考点
  • 面试题大全常见问题解析
  • AI 答疑NEW随时提问,即时解析
  • AI 模拟面试NEW模拟真实面试 + 报告
  • AI 定制路线NEW按你的简历现排
  • AI 知识地图NEW串起全站知识点
  • 原理篇React / Vue 源码拆解
  • HTTP从报文一路讲到 HTTPS
  • 浏览器渲染、事件循环、进程
  • 计算机基础Linux、网络、操作系统
  • 设计模式23 种模式怎么用
  • Node学习指南从环境搭建到服务端
  • NPM工作流script、依赖与发布
  • Docker容器化部署上手
  • Canvas图形与动画实战
  • 前端系统进阶学习大型项目工程化
  • 前端综合文章长期沉淀的实践文
  • 思维导图知识点全景图
  • 学习路线按图索骥不跑偏
  • AI 热点NEWAI 每日动态
  • 公众号动态公众号历史文章
  • 博客动态站长的技术博客
  • 开发者导航常用工具与文档站
首页程序员面试题库反转链表 迭代 三指针
数据数据结构链表栈队列

如何用迭代法反转单链表并避免断链丢失节点?

迭代反转单链表的关键是每次先保存后继节点,再修改当前节点指向,最后移动前驱和当前指针。只要严格保持该顺序,就不会丢失剩余链表。

前端进阶之旅 · 一题精讲更新于 2026.09.05
数据结构#链表栈队列#算法
先看核心答案读代码示例
理解线索

迭代反转的机制

  1. 初始化prev=null, curr=head,循环直至curr为null
  2. 保存后继next=curr.next暂存,否则改向后丢失后续节点
  3. 同步移动先令curr.next=prev,再prev=curr、curr=next

空链表和单节点无需特殊分支,循环自然返回正确结果。

核心回答

先记住这个答案

用prev初始为null,curr指向头节点,每次循环先保存next = curr.next,然后让curr.next = prev,再把prev和curr分别推进到curr和next。循环停止时,prev是新链表头。如此每个节点只遍历一次,空间仅用三个指针,时间O(n),空间O(1)。

  • 必须先保存后继再改指针
  • prev从null开始,循环完是头
  • 只遍历一次,O(1)额外内存

三指针更新顺序为何是反转命脉

若直接让curr.next = prev而不同时保留原后继,则链表从当前节点之后的部分全部丢失。因此每次循环必须先把next = curr.next记录下来。这个临时变量本质上是为下一轮准备的游标,它确保当前节点被改写后仍能到达未处理的节点。正确顺序是:保存next → 翻转curr.next → 推进prev和curr。

循环不变量是:进入循环前,prev指向已反转子链表的头,curr指向原链表剩余部分的头。每次迭代把curr接到prev之前,使不变量保持。循环结束时curr为null,prev成为整个链表的新头。由于每次操作常数时间,总时间O(n),空间O(1)。下列代码完整演示该过程。

迭代反转链表完整示例JavaScript
function ListNode(val) {
  this.val = val;
  this.next = null;
}

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

function toArray(head) {
  const arr = [];
  while (head) {
    arr.push(head.val);
    head = head.next;
  }
  return arr;
}

// build 1->2->3->4->5
const head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
console.log(JSON.stringify(toArray(reverseList(head1)))); // [5,4,3,2,1]

// empty list
const head2 = null;
console.log(JSON.stringify(toArray(reverseList(head2)))); // []

// single node
const head3 = new ListNode(7);
console.log(JSON.stringify(toArray(reverseList(head3)))); // [7]
查看输出与解释
[5,4,3,2,1]
[]
[7]

代码逐一注释了测试用例,输出验证了空链表、单节点和五节点三种情况的正确结果,时间复杂度O(n),空间复杂度O(1)。

在栈受限环境中反转长链表

某嵌入式系统需反转一条10万节点的单向消息队列,但运行环境的任务栈仅8KB,不允许递归调用。若用递归,每个调用帧约占用几十字节,深度10万必然栈溢出。迭代法只占用prev、curr、next三个指针变量,常数内存即可完成。实现时只需传入头节点,返回值作为新头,测试用例验证结果与原始顺序完全相反。

处理过程还应防御输入异常:若头节点为null则返回null,若只有一个节点则返回自身。循环中的while(curr !== null)天然涵盖这两种情况,无需另写分支。实际测试时分别用空链表、单节点和普通多节点链表检查,确保所有路径都正确。

哪些条件会导致迭代反转失效

如果链表存在环,curr永远不会变为null,循环将无限执行。反转前应先检测环,可用快慢指针,一旦发现环则中止。另外,如果链表节点被并发线程同时修改,反转过程中可能读到不一致的next,产生悬空指针。这种情况需要加锁或采用不可变节点复制方案。

还有一种隐蔽错误:交换更新顺序,先移动prev和curr再保存next,会丢失剩余节点。例如把curr = curr.next写在next = curr.next之前,后续无法继续。因此必须严格遵守保存、翻转、移动的顺序。测试时可用较长链表观察结果是否完整,并利用打印或对比数组长度来发现断链。

回答前,多想一步

容易答错的地方

先移动指针再保存next
错误:把prev = curr; curr = curr.next;写在保存next之前,导致curr.next已被改写,原后继丢失。纠正:必须先next = curr.next,再翻转curr.next,然后移动指针。
忽略空链表的特殊处理
有的写法对空链表单独判断,其实没必要。循环条件自然处理:curr为null时直接跳过,返回prev(初始为null)。但若错误地访问curr.next就会空指针异常,所以循环体必须放在while内。
试着用自己的话回答

面试官还会怎么问?

迭代反转与递归反转在时间空间上有什么差异?

迭代法时间O(n)、空间O(1);递归法时间O(n),但隐式栈空间O(n),长链表容易栈溢出。递归代码更简洁,但生产环境迭代更稳妥。

如何反转链表的指定区间(第m到n个节点)?

先遍历到第m-1个节点记录上下文,再用三指针法反转子链表,最后将子链表头尾与原链表前后部分连接。注意m=1时需更新头节点。

反转后原先的头节点如何处理?

原先的head节点最终会变成尾节点,其next应为null。在迭代中,第一次循环设其next=null,后续不会再被引用,因此正确。若忘记初始prev=null,旧头会保留原有next形成环。

从一道题,走向一组知识

把知识连起来

链表栈队列

递归反转链表时,返回值和指针翻转分别发生在递归的哪一层?

同属「链表栈队列」专题,接着看 递归 反转链表 原理 调用栈 在具体场景中的处理方式。

链表栈队列

如何每 k 个节点一组反转链表,并处理末尾不足 k 个的情况?

同属「链表栈队列」专题,接着看 k个一组反转链表 在具体场景中的处理方式。

参考资料

  • Algorithms for Competitive Programming¶

示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。

本题目录
  1. 先记住这个答案
  2. 三指针更新顺序为何是反转命脉
  3. 在栈受限环境中反转长链表
  4. 哪些条件会导致迭代反转失效
  5. 容易答错的地方
  6. 面试官还会怎么问
  7. 把知识连起来
读懂,再试着讲出来

先看核心答案,再读代码。最后展开追问,检查自己有没有遗漏边界。

试着回答追问
浏览全部面试题理解原理,也关注真实的使用场景。回到顶部 ↑