反转链表方法分享

反转链表的两种方式

1.使用递归

struct ListNode* reverseList(struct ListNode* head) {if (head==NULL || head->next == NULL) {return head;}struct ListNode* newhead=reverseList(head->next);head->next->next=head;head ->next=NULL;return newhead;
}

工作原理:这个函数使用递归来反转链表。它首先递归地反转链表的头节点之后的部分,然后修改当前节点的next指针,使其指向前一个节点。递归的基准情况是当链表为空或只有一个节点时,直接返回头节点。

空间复杂度:O(n),因为它在递归过程中使用了堆栈空间,堆栈的深度与链表的长度成正比。

时间复杂度:O(n),其中n是链表的长度,因为它需要遍历整个链表一次。

2.使用迭代

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr != NULL) {struct ListNode* nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}

工作原理:这个函数使用一个循环来反转链表。它使用三个指针:prev(前一个节点),curr(当前节点),和nextTemp(下一个节点的临时存储)。在每次迭代中,它将当前节点的next指针指向前一个节点,然后更新这三个指针,直到遍历整个链表。

空间复杂度:O(1),因为它只使用了几个额外的指针,而不依赖于链表的长度。

时间复杂度:O(n),其中n是链表的长度,因为它需要遍历整个链表一次。

总结:

递归方法在代码上看起来更简洁,但迭代方法通常在空间效率上更优,因为递归可能导致堆栈溢出,特别是对于非常长的链表,所以大家在使用时要考虑一下两者哪种更合适。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/17766.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

MySQL 数据类型

数值类型 int类型 类型说明tinyint1字节,范围从-128到127(有符号),0到255(无符号)smallint2字节,范围从-2^15到2^15-1(有符号),0到2^16-1(无符号…

【WPF】Prism学习(三)

Prism Commands 1.复合命令(Composite Commanding) 这段内容主要介绍了在应用程序中如何使用复合命令(Composite Commands)来实现多个视图模型(ViewModels)上的命令。以下是对这段内容的解释: …

用go语言后端开发速查

文章目录 一、发送请求和接收请求示例1.1 发送请求1.2 接收请求 二、发送form-data格式的数据示例 用go语言发送请求和接收请求的快速参考 一、发送请求和接收请求示例 1.1 发送请求 package mainimport ("bytes""encoding/json""fmt""ne…

SpringCloud Alibaba入门简介和Nacos服务注册和配置中心

前面已经把spring cloud相关的组件都一一学了个遍,现在有点小佩服自己…本来计划今天周末好好出去玩一圈,天气太热了,39了都,还是在办公室学习吧,进行下面的springCloud Alibaba 学习吧…不废话了赶快进入正体 1. SpringCloud Alibaba入门简介 1.1 why会出现SpringCloud alib…

如何让Excel公式中的参数实现动态引用

如果你想成为Excel函数高手,仅仅掌握VLOOKUP和Countif等函数是远远不够的,起码你得学会使用INDIRECT函数,熟练掌握INDIRECT函数能让你从一个初学者晋级为高手,学会它就好比孙悟空掌握了72般变化的基本功,你说厉不厉害。…

【流量分析】常见webshell流量分析

免责声明:本文仅作分享! 对于常见的webshell工具,就要知攻善防;后门脚本的执行导致webshell的连接,对于默认的脚本要了解,才能更清晰,更方便应对。 (这里仅针对部分后门代码进行流量…

车载诊断架构 --- 关于DTC的开始检测条件

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 所有人的看法和评价都是暂时的,只有自己的经历是伴随一生的,几乎所有的担忧和畏惧,都是来源于自己的想象,只有你真的去做了,才会发现有多快乐。…

掌握 Spring Boot 的最佳方法 – 学习路线图

在企业界,人们说“Java 永垂不朽!”。但为什么呢?Java 仍然是开发企业应用程序的主要平台之一。大型公司使用企业应用程序来赚钱。这些应用程序具有高可靠性要求和庞大的代码库。根据Java开发人员生产力报告,62% 的受访开发人员使…

《操作系统 - 清华大学》3 -3:连续内存分配:内存碎片与分区的动态分配

文章目录 0. 概述1. 内存碎片问题2. 动态分配3. 首次适配算法4. 最优适配算法5. 最差适配算法 0. 概述 内存分配是操作系统管理过程中很重要的环节,首先需要考虑的是一块连续区域分配的过程,这个过程中会有很多问题,首先比较关注的一个问题是…

MySQL学习/复习3约束

一、表的常用约束 二、null、not null 三、默认值default 3.1default与null 四、注释commen 注意事项:desc查不到注释 五、zerofill 5.1填充0以控制宽度 六、primary_key 6.1复合主键 七、auto_increment 7.1last_insert_id() 八、unique 8.1unique与primary_key …

python视频编辑中的蒙版技术:创意与技术相结合

在数字视频编辑的世界里,蒙版技术是一种强大的工具,它允许我们在视频帧上进行精确的编辑和效果叠加。通过蒙版,我们可以控制哪些部分的视频内容被显示或隐藏,从而创造出各种视觉效果和过渡。在本文中,我们将探讨如何使…

文件操作和IO

目录 一. 文件预备知识 1. 硬盘 2. 文件 (1) 概念 (2) 文件路径 (3) 文件类型 二. 文件操作 1. 文件系统操作 [1] File常见的构造方法 [2] File的常用方法 [3] 查看某目录下所有的目录和文件 2. 文件内容操作 (1) 打开文件 (2) 关闭文件 (3) 读文件 (4) 写文件 …

PCB结构与组成

PCB板就是印制电路板,又称印刷电路板,是电子元器件电气连接的提供者。PCB板转化成我们所熟悉的电路板过程如下: 了解完定义,下面是我们电路板的标识 可简单的把PCB板拆分成六个部分:导线、铺铜、过孔、焊盘、丝印、阻焊…

OrienterNet在二维公共地图实现视觉定位的模型

论文来自MetaAI: https://arxiv.org/pdf/2304.02009https://arxiv.org/pdf/2304.02009github代码: https://github.com/facebookresearch/OrienterNet?tabreadme-ov-filehttps://github.com/facebookresearch/OrienterNet?tabreadme-ov-file 研究目…

LEAN 之 多态机制(Polymorphism,Type class)简析

LEAN 通过 类型类(Type Class)来提供的多态机制(Polymorphism)。 以∅:Set α 为例,有 Set α 实现 class EmptyCollection。 其中,class EmptyCollection 定义如下: 也就是&#xf…

【微软:多模态基础模型】(1)从专家到通用助手

欢迎关注【youcans的AGI学习笔记】原创作品 【微软:多模态基础模型】(1)从专家到通用助手 【微软:多模态基础模型】(2)视觉理解 【微软:多模态基础模型】(3)视觉生成 【微…

基于java的社区捐赠物品管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术:Html、Css、Js、Vue、Element-ui 数据库:MySQL 后端技术:Java、Spring Boot、MyBatis 三、运行环境 开发工具:IDEA/eclipse 数据…

机器学习—建立表现基准

让我们来看看一些具体的数字,Jtrain和Jcv是什么,以及如何做出判断,如果学习算法具有高偏差或高方差,使用一个语音识别应用的例子作为讲解。 很多在手机上进行网络搜索的用户会使用语音识别,而不是在手机上的小键盘上打…

阮一峰科技爱好者周刊(第 325 期)推荐工具:一个基于 Next.js 的博客和 CMS 系统

近期,阮一峰在科技爱好者周刊第 325 期中推荐了一款开源工具——ReactPress,ReactPress一个基于 Next.js 的博客和 CMS 系统,可查看 demo站点。(fecommunity 投稿) ReactPress:一款值得推荐的开源发布平台 …

大学语文教材电子版(第十一版)教学用书PDF及课件

大学语文课件:https://caiyun.139.com/m/i?005CiDusEVWnR 《大学语文》(第十一版)主编:徐中玉 齐森华 谭帆。 大学语文教材电子版教师用书PDF第一课《齐桓晋文之事》艺术赏析: 孟子四处游说,养成善辩的…