0

0

c++如何实现链表反转_c++链表操作算法【源码】

尼克

尼克

发布时间:2026-02-04 14:07:02

|

951人浏览过

|

来源于php中文网

原创

不能直接交换节点值,因反转本质是修改指针而非数据;三指针迭代法最稳妥,空间O(1),需正确维护prev、curr、next;递归法要注意栈溢出、终止条件和断链防环。

c++如何实现链表反转_c++链表操作算法【源码】

反转单链表时为什么不能直接交换节点值

因为题目要求的是“链表反转”,本质是修改指针指向关系,而非仅改变数据。若只交换 val,结构未变,遇到含多个字段的自定义节点(如 nextrandom)或需保持节点内存地址不变的场景(如外部有指针引用该节点),就会出错。

用三指针迭代法反转链表最稳妥

这是面试和工程中最常采用的方式,空间复杂度 O(1),逻辑清晰,不易越界。关键在于维护三个变量:prevcurrnext,每次迭代先保存 curr->next,再让 curr->next = prev,最后推进指针。

常见错误包括:

  • 忘记在循环开始前保存 curr->next,导致链表断裂
  • prev = curr 写成 prev = curr->next,跳过节点
  • 循环条件写成 curr != nullptr 但没处理空链表,实际没问题;但若写成 curr->next != nullptr 就会漏掉最后一个节点

示例核心逻辑:

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next; // 先存下后继
        curr->next = prev;           // 反转当前指针
        prev = curr;                 // 推进 prev
        curr = next;                 // 推进 curr
    }
    return prev; // 新头结点
}

递归反转链表要注意深度和边界返回值

递归写法简洁,但隐含函数调用栈开销。对长度超过几千的链表,可能触发栈溢出(尤其在默认栈空间小的环境,如嵌入式或某些竞赛OJ)。必须确保递归终止条件严格为 head == nullptr || head->next == nullptr,否则空指针解引用会崩溃。

递归的核心在于:先走到尾部,拿到新头结点,再在回溯过程中调整指针。容易出错的是:

  • 忘记在递归调用后返回 newHead,导致函数返回随机值
  • 误写 head->next->next = head 之前未判 head->next 是否为空(其实终止条件已保证,但加空检查更鲁棒)
  • 漏设 head->next = nullptr,造成环(比如原链表 1→2→3,反转后若不置空,3→1 且 1→2→3,成环)

简版递归实现:

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

反转前务必确认链表类型和内存管理方式

标准 LeetCode 风格的 ListNode 是裸指针管理,无 RAII;但若你在项目中用 std::unique_ptr 实现链表,就不能直接用 ->next = prev,而要调用 release()reset() 来转移所有权,否则会触发 double-free 或悬垂指针。

另外,若链表节点由 new 分配,反转后仍需对应 delete,但反转本身不改变析构顺序——这点常被忽略:反转只是改指针,不等于自动释放内存。

真正容易被绕进去的地方是:你以为反转完就可以丢弃原 head 指针,但其实它现在是尾节点,若后续还要遍历到末尾做清理,得从新头出发走到底——别依赖旧变量名判断位置。

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
DeepSeek
DeepSeek

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

豆包大模型
豆包大模型

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

通义千问
通义千问

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

腾讯元宝
腾讯元宝

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

文心一言
文心一言

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

讯飞写作
讯飞写作

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

即梦AI
即梦AI

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

ChatGPT
ChatGPT

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

相关专题

更多
c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

153

2025.08.29

C++中int、float和double的区别
C++中int、float和double的区别

本专题整合了c++中int和double的区别,阅读专题下面的文章了解更多详细内容。

103

2025.10.23

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

400

2023.07.18

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

579

2023.08.10

空指针异常处理
空指针异常处理

本专题整合了空指针异常解决方法,阅读专题下面的文章了解更多详细内容。

22

2025.11.16

数据库Delete用法
数据库Delete用法

数据库Delete用法:1、删除单条记录;2、删除多条记录;3、删除所有记录;4、删除特定条件的记录。更多关于数据库Delete的内容,大家可以访问下面的文章。

279

2023.11.13

drop和delete的区别
drop和delete的区别

drop和delete的区别:1、功能与用途;2、操作对象;3、可逆性;4、空间释放;5、执行速度与效率;6、与其他命令的交互;7、影响的持久性;8、语法和执行;9、触发器与约束;10、事务处理。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

216

2023.12.29

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

425

2023.08.14

抖音网页版入口与视频观看指南 抖音官网视频在线访问
抖音网页版入口与视频观看指南 抖音官网视频在线访问

本专题汇总了抖音网页版的入口链接、官方登录页面以及视频观看入口,帮助用户快速访问抖音网页版,提供免登录访问方式和直接进入视频播放页面的方法,确保顺利浏览和观看抖音视频。

16

2026.02.04

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 6.9万人学习

前端基础到实战(HTML5+CSS3+ES6+NPM)
前端基础到实战(HTML5+CSS3+ES6+NPM)

共162课时 | 19.3万人学习

第二十二期_前端开发
第二十二期_前端开发

共119课时 | 12.7万人学习

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

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