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

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

云辰同学_2104

云辰同学_2104

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

|

991人浏览过

|

来源于php中文网

原创

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

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

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

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

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

这是面试和工程中最常采用的方式,空间复杂度 O(1),逻辑清晰,不易越界。关键在于维护三个变量:prev、curr、next,每次迭代先保存 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,否则空指针解引用会崩溃。

Blender Geometry Nodes Script Generator
Blender Geometry Nodes Script Generator

生成Blender Python (bpy)脚本,该脚本使用node_groups API和GeometryNodeTree接口程序化地创建几何节点修改器树,用于参数化3D资产生成。

下载

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

  • 忘记在递归调用后返回 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<listnode></listnode> 实现链表,就不能直接用 ->next = prev,而要调用 release() 和 reset() 来转移所有权,否则会触发 double-free 或悬垂指针。

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

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

热门AI工具

更多
Laper
Laper Hot

Laper是专为编剧、导演和制片人推出的 AI 原生剧本创作工具。

讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

WorkBuddy

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

PixPix
PixPix Hot

PixPix是一款面向电商视觉生产的AI商品图生成工具。

豆包大模型

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

Atoms
Atoms Hot

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

墨刀AI
墨刀AI Hot

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

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

DeepSeek

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

相关专题

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

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

4428

2025.08.29

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

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

844

2025.10.23

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

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

379

2026.04.23

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

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

6547

2023.07.18

堆和栈区别
堆和栈区别

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

2728

2023.08.10

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

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

179

2025.11.16

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

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

3351

2023.11.13

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

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

1025

2023.12.29

Docker Desktop怎么设置端口映射
Docker Desktop怎么设置端口映射

本专题聚焦Docker Desktop容器端口映射与访问配置,整理从创建容器、设置端口绑定到验证本地服务访问的操作流程。针对端口被占用、映射配置错误、容器服务无法访问等情况,也提供相应的检查方向,方便用户完成端口配置。

0

2026.11.03

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebSocket手册
WebSocket手册

共0课时 | 0人学习

HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 11万人学习

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

共162课时 | 29万人学习

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

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