每日一题——力扣206. 反转链表(举一反三、思想解读)
一个认为一切根源都是“自己不够强”的INTJ
个人主页:用哲学编程-CSDN博客
专栏:每日一题——举一反三
题目链接
目录
菜鸡写法编辑
代码点评
代码分析
时间复杂度
空间复杂度
专业点评
另一种方法编辑
代码点评
代码逻辑
时间复杂度
空间复杂度
专业点评
我要更强
代码点评
代码逻辑
时间复杂度
空间复杂度
点评
这种方法用到哪些哲学和编程思想
1. 迭代思想
2. 逐步构建
3. 指针操作
4. 空间效率
5. 不变性和可变性
6. 递归与迭代的对比
7. 抽象和具体化
举一反三
1. 理解数据结构的性质
2. 分步骤解决问题
3. 空间复杂度意识
4. 循环和迭代
5. 修改现有结构 vs 新建结构
6. 不变量的使用
7. 对可变性的控制
8. 边界案例和错误处理
菜鸡写法

// 定义了一个用于反转单链表的函数。接受一个指向链表头节点的指针。
struct ListNode* reverseList(struct ListNode* head) {// 如果链表为空或只有一个节点,直接返回头指针,因为无需反转。if(head==NULL||head->next==NULL)return head;// 定义三个指针用于遍历链表和反转操作。struct ListNode* tmp1=NULL;struct ListNode* tmp2=NULL;struct ListNode* newHead;// 查找链表的尾节点,将其作为新的头节点(但这个过程实际上并不改变链表结构)。for(newHead=head;newHead->next!=NULL;newHead=newHead->next) {// 空循环体,仅用于遍历到链表末尾。}// 开始反转链表的过程。for(tmp1=head,tmp2=newHead;tmp2->next!=head;) {// 查找倒数第二个节点。for(tmp1=head;tmp1->next->next!=NULL;tmp1=tmp1->next) {// 空循环体,仅用于遍历。}// 再次遍历到链表末尾的节点,这一步似乎是多余的,因为tmp2已经是最后一个节点。for(tmp2=newHead;tmp2->next!=NULL;tmp2=tmp2->next) {// 空循环体。}// 将倒数第二个节点连接到最后一个节点。tmp2->next = tmp1;// 并将倒数第二个节点的next设置为NULL,断开与前一个节点的连接。tmp1->next = NULL;}// 返回新的头节点,即原链表的尾节点。return newHead;
}
代码点评
这段代码的目标是反转一个单链表。然而,它采用了一种非常不典型且低效的方法来实现这一目标。让我们从几个方面来进行分析。
代码分析
首先,代码的基本逻辑是试图通过找到链表的最后一个节点来开始反转过程,然后逐步将每个节点移动到这个位置。这种方法虽然在逻辑上可行,但远非最优解。
时间复杂度
时间复杂度是衡量算法运行时间长短的一个指标。对于这段代码,我们注意到它包含多层嵌套循环。最外层循环的目的是为了重复反转操作,而内层的两个循环则是寻找链表的倒数第二个节点(tmp1)和最后一个节点(tmp2)。这种多层嵌套循环的使用导致了非常高的时间复杂度。
- 对于一个包含 n 个节点的链表,最外层循环需要执行 n 次,因为每次循环只能将一个节点移动到正确的位置。
- 内层循环每次都会遍历整个链表来查找倒数第二个节点,因此,它们的时间复杂度也是 O(n)。
因此,总的时间复杂度为 O(n^2),这是因为对于每个节点,算法都需要遍历整个链表来找到它应该在反转后的位置。这种方法显然不是反转链表的最佳方案。
空间复杂度
空间复杂度衡量的是算法在执行过程中需要的额外空间。这段代码的空间复杂度相对较低,为 O(1)。这是因为无论链表的大小如何,它只需要维护几个额外的指针(tmp1、tmp2 和 newHead),这些指针的数量不随链表大小变化而变化。
专业点评
从专业角度来看,这段代码虽然能够实现链表反转的功能,但其方法过于复杂且效率低下。在实际应用中,我们通常采用更高效且更直观的算法,例如迭代法或递归法,这些方法的时间复杂度为 O(n),空间复杂度为 O(1)(迭代法)或 O(n)(递归法,因为递归调用栈的使用)。
迭代法通过遍历链表一次,逐个调整节点的指向,就可以完成链表的反转,而无需如此复杂的多次遍历和无效操作。因此,尽管这段代码在逻辑上是正确的,它并不是解决问题的最佳方案。在编写代码时,寻找更高效的算法总是非常重要的,这不仅可以提升代码的运行速度,还可以提高代码的可读性和可维护性。
另一种方法
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){int arr[5001]={0},i;struct ListNode* cur=head;for(i=0;cur;cur=cur->next,i++){arr[i]=cur->val;}i--;for(cur=head;cur;cur=cur->next,i--){cur->val=arr[i];}return head;
}
代码点评
这段代码提供了一种通过使用数组作为中介来反转单链表的方法。整体上,这种方法虽然相对直观,但并不是最优解。下面是对这段代码的专业点评,包括时间复杂度和空间复杂度的分析。
代码逻辑
- **遍历链表并存储值:**初始遍历链表,将每个节点的值存储到一个固定大小的数组arr中。数组大小被设定为5001,这意味着代码假设链表的最大长度不会超过5000个节点。
- **反向赋值:**第二次遍历链表时,按反向顺序从数组arr中读取值,并重新赋值给各个链表节点。
时间复杂度
- 第一次遍历链表有一个时间复杂度为O(n),其中n是链表中的节点数量,因为它需要遍历整个链表一次。
- 第二次遍历同样有一个时间复杂度为O(n),因为它再次遍历整个链表来重新赋值。
- 因此,总体时间复杂度为O(n) + O(n) = O(2n),简化后为O(n)。
空间复杂度
- 数组arr的空间复杂度为O(m),其中m是数组的固定大小,这里是5001。尽管这个空间用于存储链表的值,但由于其大小固定,我们可以认为这里的空间复杂度是O(1),意味着与链表的长度无关。
- 没有使用递归调用或动态分配额外的数据结构,所以除了数组arr以外,没有使用额外的空间。
专业点评
- 假定限制:使用固定大小的数组(5001个元素)来存储链表的值是这段代码的一个主要限制。这意味着它只能正确处理最多5000个节点的链表。对于更大的链表,这段代码将无法工作。
- 效率和优化:虽然这种方法的时间复杂度为O(n),与一些更直接的链表反转方法相同,但它通过增加一个额外的数组来存储链表的值,这增加了额外的空间复杂度。更优的链表反转方法(例如迭代或递归反转)可以直接在链表上操作,而无需额外的存储空间。
- 实用性:这段代码在实际应用中的实用性受到限制,因为它假设了链表的最大长度。在处理未知长度的链表时,更灵活的方法是直接操作链表的指针。
总的来说,这段代码为链表反转问题提供了一个有趣的解决方案,但它不是最优的。对于实际应用,推荐使用直接在链表上操作的方法,这样可以避免固定长度数组带来的限制,并且减少空间复杂度。
我要更强
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}
代码点评
这段代码是一个用来反转单链表的经典迭代方法。它通过重新指定节点间的链接关系来实现链表的反向,不需要额外的数组或数据结构来存储链表的节点值。下面是对这段代码的专业点评,包括时间复杂度和空间复杂度的分析。
代码逻辑
- **初始化指针:**使用三个指针prev、current和next来跟踪链表的节点。prev初始化为NULL,因为反转后的链表的第一个节点将指向NULL。
- **遍历链表:**遍历整个链表,对于每个节点,暂时保存它的下一个节点(next),然后将它的next指针指向prev节点,从而实现反转。之后,prev和current都向前移动一个节点。
- **更新头指针:**遍历完成后,prev将指向原链表的最后一个节点,这时候它成了反转后的链表的头节点。更新head指针指向prev。
时间复杂度
时间复杂度是O(n),其中n是链表中的节点数。这是因为代码需要遍历链表一次,每个节点仅被访问一次。
空间复杂度
空间复杂度是O(1),因为反转过程中仅使用了有限的几个指针变量(prev、current和next),并且这个额外空间的需求不随输入链表的大小变化而变化。
点评
这种迭代方法是反转单链表的一种非常高效且空间节省的方法。与使用数组或其他数据结构存储节点值相比,这种直接操作链表指针的方法不仅节省了空间,而且简化了逻辑,提高了效率。由于它的时间复杂度是线性的,且空间复杂度是常数级别的,这使得它在实际应用中非常受欢迎,尤其是在空间资源受限的环境中。
此外,这种方法的优点还包括其简洁性和直观性,使得它容易理解和实现。不依赖于链表的大小或是其他外部数据结构,使得它在多种编程语境中都非常适用。因此,这是一种在实际编程工作中推荐使用的链表反转技术。
这种方法用到哪些哲学和编程思想
反转链表的迭代方法体现了几个重要的哲学和编程思想:
1. 迭代思想
迭代是一种通过重复执行一系列步骤直到满足某个条件来解决问题的方法。在这个链表反转的例子中,迭代思想体现在使用一个循环(while循环)来遍历链表,直到所有节点都被处理完毕。
2. 逐步构建
这种方法通过逐步改变链表节点的next指针来构建反转后的链表。这种逐步构建的思想是编程中解决复杂问题的一种常见策略,它将一个复杂的问题分解成一系列简单的步骤,每一步都依赖于前一步的结果。
3. 指针操作
链表反转方法的核心在于对指针的精确操作。指针是编程中用来直接访问和操作内存中数据的重要工具。在这个例子中,通过改变节点的next指针,实现了链表结构的改变。
4. 空间效率
这种方法的空间复杂度是O(1),意味着它只使用了常数级别的额外空间。这与许多算法和数据结构中追求空间效率的哲学相一致,特别是在资源受限的环境中,如嵌入式系统或高性能计算。
5. 不变性和可变性
在编程中,不变性指的是对象在创建后其状态不能被改变,而可变性则允许对象的状态在创建后被改变。在这个链表反转的例子中,我们利用了链表的可变性,通过改变节点的next指针来反转链表。
6. 递归与迭代的对比
虽然这个例子使用的是迭代方法,但反转链表也可以使用递归方法来实现。递归和迭代是解决问题的两种不同方法,它们各自有优缺点。在这个例子中,迭代方法避免了递归可能带来的栈溢出风险,同时也减少了额外的空间使用。
7. 抽象和具体化
链表反转的迭代方法体现了从抽象到具体化的过程。首先,我们有一个抽象的问题:反转链表。然后,我们通过具体的代码实现来解决这个问题。这种从抽象到具体的过程是编程中的一个核心思想,它帮助我们将复杂的问题分解成可管理的代码块。
总的来说,链表反转的迭代方法是一个很好的例子,展示了如何将编程思想和哲学应用于解决实际问题。它强调了迭代、逐步构建、指针操作、空间效率、不变性与可变性、递归与迭代的对比,以及抽象和具体化的重要性。
举一反三
基于单链表反转的迭代方法,以下是一些编程技巧和原则,你可以举一反三地应用到其他编程任务中:
1. 理解数据结构的性质
在反转链表之前,了解链表的性质是至关重要的。同样地,在处理任何数据结构时,首先要深入理解它的性质和运作方式。例如,数组支持随机访问,而链表支持高效的元素插入和删除。这种理解会帮助你选择正确的算法和编程策略。
2. 分步骤解决问题
反转链表的过程是一步一步完成的,每次迭代只处理一个节点。类似地,面对复杂问题时,将其拆分成一系列小任务,并逐个解决。这样可以简化问题,并保持代码的清晰和可管理性。
3. 空间复杂度意识
使用有限的几个指针变量就完成了链表的反转,这展示了在可能的情况下应该优化空间使用的重要性。在其他算法设计中,同样要考虑如何使用最小的额外空间,特别是对于大数据量或内存限制的应用场景。
4. 循环和迭代
迭代是解决问题的核心工具,不仅适用于链表操作,也适用于数组处理、树遍历等。熟练使用for
和while
循环可以帮助你编写出处理各种数据结构的有效算法。
5. 修改现有结构 vs 新建结构
在链表反转案例中,我们通过修改现有的链表结构来实现目标,而没有新建一个链表。当需要优化性能时,考虑直接修改现有结构而不是创建新的数据结构可以节省空间和时间。
6. 不变量的使用
在反转链表的过程中,我们维护了节点之间的连接关系,即使是在修改指针时。在其他问题中,识别和保持不变量可以帮助你在变化的过程中保持数据完整性和一致性。
7. 对可变性的控制
在修改数据时,要小心对数据结构中的元素进行操作,确保不会不小心破坏结构。在编程中,正确管理可变状态和不变状态对于预防错误和保证程序的可靠性至关重要。
8. 边界案例和错误处理
当你反转链表时,需要考虑空链表或只有一个节点的链表等边界情况。同样地,在设计算法和编写代码时,总是要考虑和处理边界情况和可能的错误,确保代码的健壮性。
将这些技巧和原则应用到其他编程任务中,可以帮助你更有效地解决问题,写出更清晰、更高效、更健壮的代码。
以上是本节全部内容,感谢阅读!!!
相关文章:

每日一题——力扣206. 反转链表(举一反三、思想解读)
一个认为一切根源都是“自己不够强”的INTJ 个人主页:用哲学编程-CSDN博客专栏:每日一题——举一反三题目链接 目录 菜鸡写法编辑 代码点评 代码分析 时间复杂度 空间复杂度 专业点评 另一种方法编辑 代码点评 代码逻辑 时间复杂度 空间…...

【qt】纯代码界面设计
界面设计目录 一.界面设计的三种方式1.使用界面设计器2.纯代码界面设计3.混合界面设计 二.纯代码进行界面设计1.代码界面设计的总思路2.创建项目3.设计草图4.添加组件指针5.初始化组件指针6.添加组件到窗口①水平布局②垂直布局③细节点 7.定义槽函数8.初始化信号槽9.实现槽函数…...

【深度学习】SDXL中的Offset Noise,Diffusion with Offset Noise,带偏移噪声的扩散
https://www.crosslabs.org//blog/diffusion-with-offset-noise 带有偏移噪声的扩散 针对修改后的噪声进行微调,使得稳定扩散能够轻松生成非常暗或非常亮的图像。 作者:尼古拉斯古藤伯格 | 2023年1月30日 马里奥兄弟使用稳定扩散挖掘隧道。左图显示了未…...

开发属于自己的Spring Boot Starter-18
为什么要开发专用的Spring Boot Starter Spring在通常使用时,一般是通过pom.xml文件中引入相关的jar包,然后再通过application.yml文件配置初始化bean的配置,但随着项目越来越复杂或是项目组中的应用数量越来越多,可能会带来几个…...
C中Mysql的基本api接口
一、初始化参数返回值 二、链接服务器三、执行SQL语句注意事项 四、获取结果集4.1mysql_affected_rows和mysql_num_rows4.2mysql_store_result与mysql_free_result注意事项注意事项整体的工作流程 4.3mysql_use_result()4.4mysql_field_count(…...
grafana10.x报错 Failed to upgrade legacy queries Datasource x was not found
问题 grafana 从6.x升级到10.x后,导入json文件后报错,数据源x查询不到,grafana不显示数据; Templating Failed to upgrade legacy queries Datasource x was not found解决方法 可能grafana升级后数据源找不到,在面板…...

项目管理-案例重点知识(干系人管理)
项目管理:每天进步一点点~ 活到老,学到老 ヾ(◍∇◍)ノ゙ 何时学习都不晚,加油 四、干系人管理 案例重点知识 干系人管理 案例 重点内容: (1)权力利益方格、权力影响方格ÿ…...

微信小程序踩坑,skyline模式下,scroll-view下面的一级元素设置margin中的auto无效,具体数据有效
开发工具版本 基础库 开启skyline渲染调试 问题描述 skyline模式下,scroll-view下面的一级元素的margin写auto的值是没有效果的(二级元素margin写auto是有效果的),关闭这个模式就正常显示 演示效果图 父元素的宽度和高度效果(宽度是750rpx,宽度占满的) 一级元素宽度和css效果…...

jspXMl标记语言基础
1.打开命令框进入数据库 打开eclipse创建需要连接的项目 粘贴驱动程序 查看驱动器 使用sql的包 int代表个 conlm代表列名 <%page import"java.sql.ResultSet"%> <%page import"java.sql.Statement"%> <%page import"java.sql.Connect…...
【DevOps】Linux 与虚拟局域网 (VLAN) 详解
目录 一、什么是VLAN? 二、VLAN的工作原理 三、Linux中的VLAN支持 四、内核模块 五、用户空间工具 六、创建VLAN 七、配置VLAN 八、管理VLAN 九、VLAN的应用 1、 网络隔离 2、网络管理 3、网络扩展 十、VLAN的优点和限制 十一、结论 虚拟局域网&#…...
《表格新视界:从罗列到洞察的飞跃》
在信息爆炸的当下,表格宛如一位低调的英雄,默默支撑着无数的数据世界。 曾经,我们只把表格当作简单的记录工具,一行行、一列列地填着数字与文字。但如今,表格已华丽转身,成为了展现数据魅力的舞台。 它不…...

风电功率预测 | 基于GRU门控循环单元的风电功率预测(附matlab完整源码)
风电功率预测 风电功率预测 | 基于GRU门控循环单元的风电功率预测(附matlab完整源码)完整代码风电功率预测 | 基于GRU门控循环单元的风电功率预测(附matlab完整源码) 完整代码 clc; clear close allX = xlsread(风电场预测.xlsx)...

0基础安装 composer
解决: composer 不是内部或外部命令,也不是可运行的程序 或批处理文件。 php composer.phar可以运行 安装环境:系统w11 官网地址:Composer 1.安装composer 1.1打开命令行窗口 在命令行窗口里,右键是粘贴࿰…...

MYSQL-9.问题排查
问题排查的思路与方向 问题排查思路 分析问题:根据理论知识经验分析问题,判断问题可能出现的位置或可能引起问题的原因,将目标缩小到一定范围;排查问题:基于上一步的结果,从引发问题的“可疑性”角度出发…...

制造企业数据管理:从数据到价值的转化
在数字化浪潮席卷全球的今天,制造企业面临着前所未有的机遇与挑战。如何从海量的数据中提取有价值的信息,将其转化为企业的核心竞争力,成为了每一个制造企业必须面对的问题。而数据管理,正是实现这一转化的关键所在。制造企业数据…...
单例模式介绍
【一】为什么要单例模式 单例设计模式: 一个类只允许创建一个对象(或者实例),那这个类就是一个单例类,这种设计模式就叫作单例设计模式,简称单例模式。 当一个类的功能比较单一,只需要一个实例…...

Facebook企业户/在Facebook上做推广有什么好处?
想到出海,必会想到Facebook作为世界上最大的社交网络,Facebook拥有难以想象的用户数量,流量大到没朋友。近年来也是独立站卖家获取流量的有力工具之一。独立站卖家在Facebook上做广告的好处? Facebook,Google 开企业广…...
Go GORM实战(二) | 数据库连接的N种方式
连接数据库 使用GORM连接数据库还是比较简单的,概括起来就是以下三个步骤: 引入gorm.io/gorm和对应数据库的驱动库,如gorm.io/driver/sqlite。 调用对应驱动库的Open()或New()函数返回一个实现了gorm.Dialector接口的实例。 调用gorm.Open…...
Cocos Creator 2D Mask与Layout 使用详解
Cocos Creator是一款强大的2D游戏开发引擎,提供了丰富的功能和工具,使开发者可以轻松创建出高质量的游戏。其中,2D Mask和Layout是Cocos Creator中常用的两个组件,它们可以帮助开发者实现更加复杂和精美的游戏界面设计。本文将详细…...
项目-坦克大战
增加功能 我方坦克在发射的子弹消亡后,才能发射新的子弹。同时实现发多颗子弹 1,在按下J键,我们判断当前hero对象的子弹,是否已经销毁2,如果没有销毁,就不去触发shotEnemyTank3,如果已经销毁&…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
Python实现简单音频数据压缩与解压算法
Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中,压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言,提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...