0

0

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

尼克

尼克

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

|

1003人浏览过

|

来源于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++免费学习笔记(深入)”;

ithy
ithy

融合多种AI模型的AI搜索平台

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

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

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

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

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

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

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

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

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

热门AI工具

更多
DeepSeek
DeepSeek

幻方量化公司旗下的开源大模型平台

豆包大模型
豆包大模型

字节跳动自主研发的一系列大型语言模型

通义千问
通义千问

阿里巴巴推出的全能AI助手

腾讯元宝
腾讯元宝

腾讯混元平台推出的AI助手

文心一言
文心一言

文心一言是百度开发的AI聊天机器人,通过对话可以生成各种形式的内容。

讯飞写作
讯飞写作

基于讯飞星火大模型的AI写作工具,可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

即梦AI
即梦AI

一站式AI创作平台,免费AI图片和视频生成。

ChatGPT
ChatGPT

最最强大的AI聊天机器人程序,ChatGPT不单是聊天机器人,还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

相关专题

更多
if什么意思
if什么意思

if的意思是“如果”的条件。它是一个用于引导条件语句的关键词,用于根据特定条件的真假情况来执行不同的代码块。本专题提供if什么意思的相关文章,供大家免费阅读。

823

2023.08.22

while的用法
while的用法

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

103

2023.09.25

printf用法大全
printf用法大全

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

76

2023.06.20

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

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

298

2023.11.28

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

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

183

2023.11.23

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

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

117

2025.11.27

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

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

1536

2023.10.19

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

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

423

2025.10.17

pixiv网页版官网登录与阅读指南_pixiv官网直达入口与在线访问方法
pixiv网页版官网登录与阅读指南_pixiv官网直达入口与在线访问方法

本专题系统整理pixiv网页版官网入口及登录访问方式,涵盖官网登录页面直达路径、在线阅读入口及快速进入方法说明,帮助用户高效找到pixiv官方网站,实现便捷、安全的网页端浏览与账号登录体验。

776

2026.02.13

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C# 教程
C# 教程

共94课时 | 9.8万人学习

C 教程
C 教程

共75课时 | 4.9万人学习

C++教程
C++教程

共115课时 | 18.6万人学习

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

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号