【leetcode 力扣刷题】反转链表+递归求解
反转链表+递归求解
- 206. 反转链表
- 解法①:取下一个节点在当前头节点前插入
- 解法②:反转每个节点next的指向
- 解法③:递归
- 92.反转链表Ⅱ
- 反转left到right间节点的next指向
- 234.回文链表
- 解法①:将链表元素存在数组中,在数组上判断回文
- 解法②:在链表上反转前半部分链表,和后半部分对比
- 解法③:==递归==
206. 反转链表
题目链接:206.反转链表
题目内容:
理解题意:没有特殊要求,就是把链表反转,相当于从之前的末尾指向开头。
解法①:取下一个节点在当前头节点前插入
第一种方法最容易想到,从前往后遍历链表的同时,每次从原链表中取下当前节点,插入到新链表的开头。 这里的新链表,实际就是该节点之前所有节点已经反转后构成的链表,过程如下:
5
代码如下(C++):
//依次取出每个节点,并将其插入在新链表的头部
class Solution {
public:ListNode* reverseList(ListNode* head) {//如果链表为空直接返回空指针if(!head)return nullptr;ListNode *currNode = head;//初始化新链表,为空ListNode *newhead = nullptr;while(currNode != nullptr){ ListNode *tmp = currNode->next;// currNode插入在新链表的头部currNode->next = newhead; newhead = currNode;//currNode移到下一个节点currNode = tmp; }//返回新链表return newhead;}
};
解法②:反转每个节点next的指向
假设原链表中一前一后两个节点:preNode和currNode,指向是preNode->next = currNode;反转后链表中这俩节点的指向是currNode->next = preNode。既然如此,那么可以在遍历链表中节点的时候【当前节点就用currNode】,直接改变其指针域:
代码如下(C++):
//遍历链表每个节点,将next改变成指向前面;
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = NULL; //prev前驱节点初始化为nullListNode* currNode = head; //当前节点初始化为头节点while(currNode){ListNode* tmp = currNode->next;//改变当前节点指针,指向其前驱节点currNode->next = prev;//prev和currNode都向后移动,遍历链表节点prev = currNode;currNode = tmp;}return prev; //最后prev就是新的head,currNode已经为null了}
};
本质上解法①和解法②是一样的,只是从两个角度去理解“反转”。
解法③:递归
从前往后遍历链表节点,并使用递归方法的时候,要到最后一个节点才开始往前返回,那么就是先反转后半截链表,再向前返回到当前的节点,再对当前节点处理。假设链表有k个节点:
- 递归到第k个节点的时候,递归终止,并且这最后一个节点就是整个链表反转后的头节点,直接返回该节点地址;
- m+1个节点作为后半截已经反转后的链表的尾节点,其next指向null;现在将m+1和m个节点连接起来,m+1的next指向m;m+1个节点是后半截反转后的尾节点,怎么找到m+1个节点呢? 【对于当前第m个节点,其next依然指向m+1个节点,因此直接currNode->next->next = currNode,使m+1个节点的next指向当前第m个节点】;
- m现在作为m-1之后剩余链表反转后的尾节点,其next应该指向null;
- 到第m个节点的时候,m+1~k个节点已经反转了,并返回了新的头节点;即便是加上第m个节点并反转,第m个节点也是加在反转后链表的尾部,因此上一步返回的新头节点是整个链表反转后头节点,因此要一直向前返回这个地址;
整个过程如图所示:
代码如下(C++):
class Solution{
public:ListNode* reverseList(ListNode* head) {//如果链表为空,直接返回//如果已经遍历到最后一个节点,最后一个节点就是反转后的头节点,直接返回if(head == nullptr || head->next == nullptr)return head;//当前head之后的链表已经反转了,并返回反转后的新头节点指针 ListNode *newhead = reverseList(head->next);//将head->next的next指针指向当前head,反转head->next->next = head;//断开当前head和head->next之间原本的连接head->next = nullptr;//返回的新头节点是整个链表反转后的头节点,因此一直返回newheadreturn newhead;}
};
92.反转链表Ⅱ
题目链接:92.反转链表Ⅱ
题目内容:
理解题意:在对整个链表反转的基础上,增加了限制条件——只反转给定的left~right位置间的节点。 完成left~right的反转后,还需要让left之前的节点left_pre->next指向right;还需要让left->next指向right->next。
以下解法为一遍访问链表完成left~right之间的节点的反转:
反转left到right间节点的next指向
整个过程分为以下几步:
- 需要记录的节点有left、right、left前面一个节点left_pre和right后面一个节点right->next;
- 先遍历链表找到left_pre和left;
- 从left开始到right,用反转链表题目的解法,反转这一段链表;用到pre和currNode两个变量保存当前要改变指向的节点、以及之前的一个节点;
- 上一步循环结束时,pre就是right,currNode就是right->next; 此时建立新连接:left_pre->next = right【即pre】,left->next = right->next【即currNode】; 得到完整链表;
上述过程为一次遍历链表,在遍历的过程中改变left~right间的指向。全部代码如下(C++):
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {//如果left和right相等,没有节点要反向if(left == right) return head;//存left和left前面一个节点的地址ListNode *leftNode = head, *left_prev = NULL;//定位到leftNode,并保存left_prefor(int i=1; i<left && leftNode; i++ ){left_prev = leftNode;leftNode = leftNode->next;} //left~right间反向时用到的变量 ListNode *prev, *currNode; //当前节点和当前节点的前一个节点 prev = leftNode;currNode = prev->next;while(currNode && left < right){ListNode* tmp = currNode->next;//反转next指向currNode->next = prev;//pre和currNode都向前移动,遍历left~right间节点prev = currNode;currNode = tmp;left++;} //循环结束后pre是right节点,currNode是right->next节点//左边节点leftNode指向right->nextleftNode->next = currNode;//判断leftnode是不是头节点if(left_prev != NULL) //如果不是,left前面一个节点指向right节点left_prev->next = prev;else //如果是,新的头节点就是right节点head = prev; return head;}
};
234.回文链表
题目链接:203.回文链表
题目内容:
理解题意:实际就是判断是不是回文【回文数:从前往后、从后往前是一样的,比如0123210;判断:两个指针一个开头,一个结尾,逐个对比,全相等就是回文】,只是换成了在链表上判断。 但是由于链表只能向next一个方向遍历,不像数组、string等可以用下标index去定位。因此有两种解法:
- 遍历链表,并且把链表各个节点的val按照顺序存在vector里面,然后在vector上比较;
- 直接在链表上比较;
直接在链表上进行比较又有两种方法:
- 遍历链表的同时,用上面的反转链表方法,把前半部分链表反转;反转后的前半部分链表和后半部分链表的节点逐个对比,val值都一样即为回文;
- 递归求解:因为递归到最后一个节点才递归终止,能够知道当前的节点的val;一开始的head还在开头,就能实现首尾比较;一旦不相等,其他节点就不用比较了,直接向前返回false;如果相等,后面的节点向前返回到前面一个节点进行操作,前面节点需要向后移动;
解法①:将链表元素存在数组中,在数组上判断回文
这个方法最好理解,也没有什么难度,先遍历链表取出各个节点的val,按原顺序存在vector中,在vector上实现回文判断,需要额外的空间……
代码如下(C++):
class Solution {
public:bool isPalindrome(ListNode* head) {vector<int> val; //数组用于存储链表节点的valListNode *currNode = head;//遍历链表节点,并保存各个节点的valwhile(currNode){val.emplace_back(currNode->val);currNode = currNode->next;}//双指针,判断数组是否是回文的for(int i = 0, j = val.size() - 1; i < j ; i++,j--){//一旦有节点不相等,就不是回文if(val[i] != val[j])return false;}return true;}};
解法②:在链表上反转前半部分链表,和后半部分对比
这个方法是一次遍历链表,遍历的过程中,同时反转链表,这个反转结束的地方是链表的中间点; 从这个中间点开始,用一个指针逐个向前访问前面一段链表的节点,再用一个指针逐个向后访问后面一段链表的节点;并比较节点的val,判断是否是回文,过程如下所示:
这里有个问题,就是如何找到链表的中间节点:用一个slow指针,一个fast指针,初始slow和fast都为head【没有附加头结点时】,每次slow向后移动一个slow = slow->next,但是fast向后移动两个fast = fast->next->next。当fast->next =null的时候【有偶数个节点】或fast->next->next = null的时候【有奇数个节点】终止,此时的slow就定位在中间节点。
代码实现(C++):
class Solution {
public:bool isPalindrome(ListNode* head) {//如果只有一个节点直接返回trueif(head->next== nullptr)return true;//用slow、fast来寻找链表的中间点,prev是slow前面一个节点,辅助完成反转操作 ListNode *slow = head,*fast = head, *prev = NULL;//找到中间节点,并同时反转前半段链表while(fast->next && fast->next->next){ fast = fast->next->next; ListNode* tmp = slow->next;slow->next = prev;prev = slow;slow = tmp; } //上述循环结束时,slow是(n+1)/2节点//比如5个节点,slow在第3个节点;6个节点,slow在第3个节点//且此时slow指向是原始的指向ListNode *right_head, *left_head; //左右两段一段向前,一段向后链表的头节点right_head = slow->next; //右边头节点就是slow->next//偶数个节点,slow需要反转连接if(fast->next){ slow->next = prev;left_head = slow;}//奇数个节点,slow不需要反转连接else{ left_head = prev; }//两段链表节点逐个对比valwhile(left_head!=nullptr && right_head!=nullptr){if(left_head->val != right_head->val)return false;left_head = left_head->next;right_head = right_head->next;}return true;}
};
其中奇数个节点、偶数个节点需要分开讨论,写代码的时候要区分开。
解法③:递归
这里的递归求解参考的力扣官方题解。因为递归到最后一个节点才递归终止,能够知道当前的节点的val;一开始的frontNode还在开头,就能实现首尾比较;一旦不相等,其他节点就不用比较了,直接向前返回false;如果相等,后面的节点向前返回到前面一个节点进行操作,前面节点需要向后移动;
递归的时候需要一个指针,递归到最后向前返回;那么还需要一个外部指针,递归返回后,它向后移动。
代码实现(C++):
class Solution {
public:ListNode* frontNode; //需要定义一个全局的变量bool recursivelyCheck(ListNode *currNode){if(currNode){//后面已经有节点和前面的不相等,中间一截不用比较了直接向上返回falseif(!recursivelyCheck(currNode->next))return false;//对比当前元素与前面对应元素是否一样if(currNode->val != frontNode->val)return false;//将前面元素向后面移动一个frontNode = frontNode->next;}return true;}bool isPalindrome(ListNode* head) {frontNode = head; return recursivelyCheck(head);}
};
相关文章:

【leetcode 力扣刷题】反转链表+递归求解
反转链表递归求解 206. 反转链表解法①:取下一个节点在当前头节点前插入解法②:反转每个节点next的指向解法③:递归 92.反转链表Ⅱ反转left到right间节点的next指向 234.回文链表解法①:将链表元素存在数组中,在数组上…...
一文读懂Redis配置,史上真香配置
文章目录 基本配置项AOF持久化配置项RDB持久化配置项淘汰策略配置项主从复制配置项鸣谢 让那些总为redis连接异常的小白指引明灯,少走弯路。为那些不知道如何进行高级配置的大佬整一杯小酒。 基本配置项 bind:用于设置Redis绑定的IP地址。默认情况下&…...

maven打出jar中动态替换占位符
使用场景: maven打出的jar中pom.xml动态替换占位符 有些时候某些公共工具jar包被项目引用后发现公共jar的pom.xml中的version依然还是占位符,例如下面 <dependency><groupId>org.projectlombok</groupId><artifactId>lombok<…...
【Git游戏】通过游戏重新学习Git
在提交树上移动 HEAD HEAD:一个标志符号(通常情况下指向当前分支,间接指向当前最新的提交记录) 可以通过git checkout commitID从而指向提交记录 commitID 本身是一串哈希值(基于 SHA-1,共 40 位) 我们在…...
如何通过以太坊JSON-RPC方式获取ERC-20代币的信息?
目录 一、ERC-20介绍 二、ERC-20代币标准功能 1、可选功能 2、标准功能 三、获取代币信息...

线性代数的学习和整理4: 求逆矩阵的多种方法汇总
目录 原始问题:如何求逆矩阵? 1 EXCEL里,直接可以用黑盒表内公式 minverse() 数组公式求A- 2 非线性代数方法:解方程组的方法 3 增广矩阵的方法 4 用行列式的方法计算(未验证) 5 A-1/|A|*A* &…...

【C#学习笔记】匿名函数和lambda表达式
文章目录 匿名函数匿名函数的定义匿名函数作为参数传递匿名函数的缺点 lambda表达式什么是lambda表达式闭包 匿名函数 为什么我们要使用匿名函数?匿名函数存在的意义是为了简化一些函数的定义,特别是那些定义了之后只会被调用一次的函数,与其…...
百度Apollo:引领自动驾驶技术创新的先锋
文章目录 前言一、内容总结 前言 大家好,我是萝卜头不吃萝卜头,今天和大家分享一下我学习百度Apollo自动驾驶的心得。 在七月份的时候,我收到了Apollo开发者社区的邀请,进行学习Apollo自动驾驶汽车的2023星火培训训练,…...

Redis 重写 AOF 日志期间,主进程可以正常处理命令吗?
重写 AOF 日志的过程是怎样的? Redis 的重写 AOF 过程是由后台子进程 bgrewriteaof 来完成的,这么做有以下两个好处。 子进程进行 AOF 重写期间,主进程可以继续处理命令请求,从而避免阻塞主进程子进程带有主进程的数据副本。这里…...

java实现生成RSA公私钥、SHA256withRSA加密以及验证工具类
前言: RSA属于非对称加密。所谓非对称加密,需要两个密钥:公钥 (publickey) 和私钥 (privatekey)。公钥和私钥是一对,如果用公钥对数据加密,那么只能用对应的私钥解密。如果用私钥对数据加密,只能用对应的公…...

lab7 thread
文章目录 Uthread: switching between threadstaskhints思路上下文的恢复和保存thread_createthread_schedule Using threads思路 Barrier Uthread: switching between threads 在这个练习中,你将为一个用户级别线程系统设计上下文切换机制,并实现它。 …...

接口自动化测试:mock server之Moco工具
什么是mock server mock:英文可以翻译为模仿的,mock server是我们用来解除依赖(耦合),假装实现的技术,比如说,前端需要使用某些api进行调试,但是服务端并没有开发完成这些api&#…...

用python从零开始做一个最简单的小说爬虫带GUI界面(2/3)
目录 前一章博客 前言 主函数的代码实现 逐行代码解析 获取链接 获取标题 获取网页源代码 获取各个文章的链接 函数的代码 导入库文件 获取文章的标题 获取文章的源代码 提取文章目录的各个文章的链接 总代码 下一章内容 前一章博客 用python从零开始做一个最简单…...
CEF 缓存处理:清理缓存、禁用缓存、忽略缓存
目录 一、CEF缓存处理 1、指定缓存路径 2、清理缓存 3、禁用缓存 1)、原理分析...

Android 系统桌面 App —— Launcher 开发(1)
Android 系统桌面 App —— Launcher 开发(1) Launcher简介 Launcher就是Android系统的桌面,俗称“HomeScreen”也就是我们开机后看到的第一个App。launcher其实就是一个app,它的作用是显示和管理手机上其他App。目前市场上有很…...

一个程序员的工作日记--每天就干两件事,一年后让别人刮目相看
文章目录 成功源于专注一、早上布局二、晚上复盘三、技术细节四、专注与成功五、专注的重要性六、忙碌和赚钱七、结论以嵌入式开发为例:一、早上布局二、晚上复盘三、技术细节四、专注与成功五、忙碌和赚钱六、结论在嵌入式软件开发中,我们需要按照以下步…...

Linux虚拟机安装(Ubuntu 20)
最近这段时间使用VMWare安装了一下Ubuntu版本的Linux虚拟机,在这里记录一下安装时参考的文章以及需要注意的细节 参考链接: VMware虚拟机下安装Ubuntu20.04(保姆级教程) 一、安装VMWare 下载链接:VMware Workstatio…...

1.6 服务器处理客户端请求
客户端进程向服务器进程发送一段文本(MySQL语句),服务器进程处理后再向客户端进程发送一段文本(处理结果)。 从图中我们可以看出,服务器程序处理来自客户端的查询请求大致需要经过三个部分,分别…...

火山引擎发布自研视频编解码芯片 压缩效率提升30%
8月22日,火山引擎视频云宣布其自研的视频编解码芯片已成功出片。经验证,该芯片的视频压缩效率相比行业主流硬件编码器可提升30%以上,未来将服务于抖音、西瓜视频等视频业务,并将通过火山引擎视频云开放给企业客户。 火山引擎总裁…...

从头开始:将新项目上传至Git仓库的简易指南
无论您是一个经验丰富的开发者还是一个刚刚起步的新手,使用Git来管理您的项目是一个明智的选择。Git是一个强大的版本控制系统,它可以帮助您跟踪项目的变化、合并代码以及与团队成员协作。在本文中,我们将为您提供一步步的指南,教…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...

elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...