讲师中心 微信公众号
AI工具推荐 视频效率加速

C++怎么实现单向链表反转_C++算法面试教程【经典】

小宇吖_1404

小宇吖_1404

发布时间:2026-02-20 13:14:02

|

1023人浏览过

|

来源于php中文网

原创

单向链表原地反转需用prev、cur、next三指针,先暂存cur->next再改指向,循环结束prev为新头;须判空链表和单节点,while条件用cur避免空指针解引用;递归法简洁但栈溢出风险高,返回值才是新头不可误用原head。

c++怎么实现单向链表反转_c++算法面试教程【经典】

用 next 指针原地翻转,别新建节点

单向链表反转本质是把每个节点的 next 指向“调个头”,从指向后一个变成指向前一个。最常见错误是边遍历边改 next 却丢了后续节点——比如写成 cur->next = prev; cur = cur->next;,这时 cur 已经变成 prev,链表断了。

正确做法是提前存好下一个节点:

  • 用三个指针:prev(已反转部分头)、cur(当前处理节点)、next(暂存 cur->next)
  • 每轮先 next = cur->next,再 cur->next = prev,最后 prev = cur; cur = next;
  • 循环结束时 prev 就是新头节点

nullptr 判空和边界情况必须检查

空链表(head == nullptr)和单节点链表(head->next == nullptr)都应直接返回 head。漏掉这些,代码在面试或单元测试里一跑就崩。

典型错误现象:Segmentation fault (core dumped),尤其在 while 循环条件里只写 cur != nullptr 却没保证 cur 非空就访问 cur->next。

立即学习“C++免费学习笔记(深入)”;

C++ Code Review Master
C++ Code Review Master

组合式C++代码评审方案,融合静态分析、AI推理、多轮迭代评审和C++专项检查,适用于PR审查、增量代码审查、全项目评审和代码质量评分,触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载
  • 入口第一行加 if (!head) return head;
  • while 条件用 cur 而非 cur->next,避免解引用空指针
  • 反转后记得把原头节点的 next 设为 nullptr(虽然循环中已自然完成,但显式写更稳)

递归写法简洁但栈空间有风险

递归版本代码短:找到尾节点返回它作为新头,回溯时改当前节点的 next->next 和 next。但它隐式用了 O(n) 栈深度。

实际工程中,链表稍长(比如上万节点)就可能栈溢出;面试时若不说明限制,容易被追问“如果链表超长怎么办”。

  • 递归终止条件必须是 head == nullptr || head->next == nullptr
  • 关键两步:先 newHead = reverseList(head->next),再 head->next->next = head; head->next = nullptr;
  • 别忘了最后返回 newHead,不是 head

反转后原 head 不再是头,别误用

这是最容易被忽略的语义陷阱。反转完成后,原来的 head 节点变成了尾节点,它的 next 是 nullptr。如果后续代码还拿 head 当头去遍历或释放,会只处理一个节点甚至崩溃。

  • 函数返回值才是新链表头,必须用返回值继续操作
  • 调试时可用 printf 或日志打一下新头节点的值,确认是否真翻过来了
  • 若需保持接口不变(比如函数 void 类型),得传入二级指针或引用参数来更新头指针

链表反转看着简单,真正写对要同时盯住指针指向、内存访问顺序、边界判空三件事。少一个,运行时就给你颜色看。

热门AI工具

更多
墨刀AI
墨刀AI Hot

一款AI图像与设计工具,主要用于产品经理的专属智能体,适合需要提升相关任务效率的用户。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

火山引擎

火山引擎是一款面向企业的云计算与AI服务平台。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

AionClaw
AionClaw Hot

AionClaw是一款面向办公、创作和编程任务的AI桌面智能体。

UP简历
UP简历 Hot

一款AI办公效率工具,主要用于基于AI技术的免费在线简历制作工具,适合需要提升相关任务效率的用户。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

相关专题

更多
while的用法
while的用法

while的用法是“while 条件: 代码块”,条件是一个表达式,当条件为真时,执行代码块,然后再次判断条件是否为真,如果为真则继续执行代码块,直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容,供大家免费下载体验。

334

2023.09.25

printf用法大全
printf用法大全

php中文网为大家提供printf用法大全,以及其他printf函数的相关文章、相关下载资源以及各种相关课程,供大家免费下载体验。

708

2023.06.20

fprintf和printf的区别
fprintf和printf的区别

fprintf和printf的区别在于输出的目标不同,printf输出到标准输出流,而fprintf输出到指定的文件流。根据需要选择合适的函数来进行输出操作。更多关于fprintf和printf的相关文章详情请看本专题下面的文章。php中文网欢迎大家前来学习。

1009

2023.11.28

javascriptvoid(o)怎么解决
javascriptvoid(o)怎么解决

javascriptvoid(o)的解决办法:1、检查语法错误;2、确保正确的执行环境;3、检查其他代码的冲突;4、使用事件委托;5、使用其他绑定方式;6、检查外部资源等等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

636

2023.11.23

java中void的含义
java中void的含义

本专题整合了Java中void的相关内容,阅读专题下面的文章了解更多详细内容。

351

2025.11.27

C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

339

2026.04.23

硬盘接口类型介绍
硬盘接口类型介绍

硬盘接口类型有IDE、SATA、SCSI、Fibre Channel、USB、eSATA、mSATA、PCIe等等。详细介绍:1、IDE接口是一种并行接口,主要用于连接硬盘和光驱等设备,它主要有两种类型:ATA和ATAPI,IDE接口已经逐渐被SATA接口;2、SATA接口是一种串行接口,相较于IDE接口,它具有更高的传输速度、更低的功耗和更小的体积;3、SCSI接口等等。

3088

2023.10.19

PHP接口编写教程
PHP接口编写教程

本专题整合了PHP接口编写教程,阅读专题下面的文章了解更多详细内容。

4569

2025.10.17

LLVM自定义Pass怎么写
LLVM自定义Pass怎么写

本专题聚焦LLVM自定义Pass开发,整理Pass类结构、run()方法、PreservedAnalyses、CMake构建、插件注册、-load-pass-plugin加载和测试用例编写流程。

100

2026.09.30

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Conan 2 Essentials 免费课程
Conan 2 Essentials 免费课程

共0课时 | 0人学习

CMake 与 Conan 集成实践
CMake 与 Conan 集成实践

共0课时 | 0人学习

Conan 2 高级依赖模型介绍
Conan 2 高级依赖模型介绍

共0课时 | 0人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn