数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)
目录
一.前言
二.leetcode160. 相交链表
1.问题描述
2.问题分析与求解
三.leetcode141. 环形链表
1.问题描述
2.代码思路
3.证明分析
下一题会用到的重要小结论:
四.leetcode142. 环形链表 II
1.问题描述
2.问题分析与求解
Judgecycle接口:
方法一:
方法二:
一.前言
单链表和带环单链表OJ题是笔试面试常考的题目,本期是关于带环单链表基础题的刷题小笔记(前两个题的求解过程可以用于求解第三个题哦!)
二.leetcode160. 相交链表
leetcode链接:160. 相交链表 - 力扣(Leetcode)
1.问题描述
给你两个单链表的头节点的地址
headA
和headB
,请你找出并返回两个单链表相交部分的起始节点。如果两个链表不存在相交节点,返回null
。比如图示两个链表:
已知a1和b1的地址,编写程序返回c1的地址。
- 测试用例中的链表不存在环
- 函数返回结果后,两个链表必须保持其原始结构
题解接口:
class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {} };
2.问题分析与求解
方法一:
- 先各自求出两个链表的长度,并求出它们长度的差值:
- 然后再用两个指针来分别遍历两个链表,其中遍历较长链表的指针要先向前走N步(N表示两个链表长度的差值),然后两个指针再一起向前遍历两个链表,若链表存在交点,则两个指针必定会在交点相遇:
题解代码:
class Solution { public:int countNode(ListNode * head) //封装一个求节点个数的函数{int count = 0;while(head){count++;head=head->next;}return count;}ListNode * foundNode(ListNode* longlist,ListNode* shortlist,int diff)//封装一个求第一个相交节点的函数{while(diff) //遍历长链表的指针先向前走diff步{longlist = longlist->next;--diff;}while(longlist && shortlist) //两指针一起向前走直到相遇或指向空指针{if(longlist == shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}return nullptr; //最终指向空指针则说明两表不相交}ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int countA = countNode(headA);int countB = countNode(headB);if(countA>=countB){return foundNode(headA,headB,countA-countB);}else{return foundNode(headB,headA,countB-countA);}} };
这个方法思路比较简单但是不够简洁优雅,还有一个更简洁优雅的解法。
方法二:
- 我们先考虑遍历表A的指针:当遍历表A的指针走到尾节点后,我们令其返回指向表B的头节点,此后如果该指针继续向前走countB步,则指针会来到两个链表的第一个相交节点,此时遍历表A的指针总共向前走了(countA + public + countB)次,如图:
- 类似地,遍历B表的指针走到表尾后,我们令其返回指向表A的头节点,此后如果该指针再向前走countA步则同样会来到两表的第一个相交节点.此时遍历B表的指针同样总共向前走了(countA+countB+public)次.
- 因此如果我们让遍历表A和表B的指针同时向前遍历链表,当他们走到表尾后,则令他们返回指向另外一个链表的头节点,两指针最终必定会在两链表第一个相交节点相遇(此时两个指针同时向前走了(countA + countB + public)次)。如图:
题解代码:
class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * ptrA = headA;ListNode * ptrB = headB;while(ptrA!=ptrB){ptrA = (ptrA==nullptr)? headB : ptrA->next; //(ptrA==nullptr)代表指针指向A表尾ptrB = (ptrB==nullptr)? headA : ptrB->next; //(ptrB==nullptr)代表指针指向B表尾}return ptrA;} };
- 若两个链表不相交,最终两个指针会同时变为空指针,函数会返回空指针
三.leetcode141. 环形链表
141. 环形链表 - 力扣(Leetcode)
1.问题描述
给你一个链表的头节点的地址
head
,判断链表中是否有环。(如果链表中有某个节点,可以通过连续跟踪
next
指针再次到达,则链表中存在环.)如果链表中存在环 ,则返回
true
。 否则,返回false
。比如:
题解接口:
class Solution { public:bool hasCycle(ListNode *head) {} };
2.代码思路
本题的代码思路很简单,利用的是快慢指针法,两个指针同时遍历链表,快指针一次走两步,慢指针一次走一步。
- 如果链表中不存在环,则快指针会率先达到表尾。
- 如果链表中存在环,则快慢指针最终会在环中相遇。
题解代码:
class Solution { public:bool hasCycle(ListNode *head) {if(nullptr == head || nullptr == head->next)//单节点和无节点链表做额外判断{return false;}ListNode* fast = head->next->next; //让快指针先走两步,慢指针走一步让它们指向不同节点ListNode* slow = head->next;while((fast && fast->next && fast!=slow)){fast=fast->next->next; //快指针一次走两步slow=slow->next; //慢指针一次走一步}return (fast==slow)? true : false; //判断两指针是否相遇并确定返回值(若无环fast一定不等 //slow)} };
然而本题的关键并不在于代码如何写,而是在于如何去证明上述求解思路的合理性。
接下来我们尝试对快慢指针法在本题中的合理性做一个比较严格的证明。
3.证明分析
下文的所谓的距离指的是两个链表节点位置之间指针链的数目。
- 我们先将带环链表用一个概念图表示一下:
![]()
- 我们令快慢指针同时从链表头节点出发:(fast=fast->next->next表示快指针一次走两步)(slow=slow->next表示慢指针一次走一步)
- 如果链表中不存在环,易知快指针fast必然率先结束遍历链表的过程(fast或fast->next指向空),此时返回false。
- 如果链表中存在环,那么快指针会率先进环,之后慢指针入环时,快指针此时一定处于环中某个位置:
- 此后快指针开始在环中追赶慢指针,假设慢指针入环时,快指针与慢指针的距离为N(N小于或等于环的总长度减一)(N为某一个正整数)
- 慢指针入环时两指针的环上距离是整数N.快指针每次循环前进两步,慢指针每次循环前进一步,可知两个指针的距离每次循环后会缩小1,则快指针必定会在环上某个点与慢指针相遇(即fast==slow,此时说明链表中存在环)
下一题会用到的重要小结论:
- 另外还有一个重要小结论:快慢指针相遇时,慢指针在环上走过的距离一定小于环的长度(因为N小于或等于环的总长度减一) (该结论在下一题中会用到)
更进一步的思考:我们能否规定快指针一次走三步或者n步(n>2)呢?
- 答案是否定的,我们可以规定让快指针一次走三步来做一下分析,设当慢指针刚入环时,两个指针的距离为N:
- 快指针一次走三步,那么每次循环两个指针的距离会缩小2
- 假如N是偶数,那么快指针最终会与慢指针相遇
- 假如N是奇数,那么快指针追上慢指针后会处于慢指针的前一个位置。(整除余1)
- 此时快指针重新开始追赶慢指针:设环的长度为X,则此时相当于快指针与慢指针的距离为X-1
- 若X-1为偶数,那么快指针最终可以与慢指针相遇
- 若X-1为奇数,那么快指针追上慢指针后会又一次处于慢指针的前一个位置。紧接着就开始了无限循环追赶,两个指针永远都不会相遇
- 同样地,若令快指针一次走3,4,5...n步,通过数学归纳思维,我们同样能分析出(在各种不同的环长度的链表中)可能会出现上述类似的无限追赶的情况,因此可以得出结论:快指针每次必须比慢指针多走1步才能确保(在任何带环链表中)两指针最终在环中会相遇。
四.leetcode142. 环形链表 II
142. 环形链表 II - 力扣(Leetcode)
1.问题描述
该题在上一题的基础上,要求我们编写的接口能够返回链表开始入环的第一个节点的地址。如果链表无环,则返回
nullptr.
比如:
题解接口:
class Solution { public:ListNode* Judgecycle(ListNode* head){} };
2.问题分析与求解
第一步:
本题的求解建立在上一个题目的基础之上.
我们先编写一个接口,用于判断链表是否带环,并且返回快慢指针在环中相遇位置节点的地址(链表不带环则返回空指针)。
Judgecycle接口:
ListNode* Judgecycle(ListNode* head){if(nullptr==head || nullptr == head->next){return nullptr;}ListNode *fast =head->next->next;ListNode *slow = head->next;while(fast && fast->next && fast!=slow){fast=fast->next->next;slow = slow ->next;}return (fast&&fast->next)? fast : nullptr;//(fast或fast->next为空则表示链表无环)} //(为空说明fast走到表尾)
- 若链表带环,返回的fast指针就是快慢指针在环中相遇的位置的节点的地址
- 该接口的原理参见上一题的分析。
- 在题解接口中我们用一个temmet指针来接收Judgecycle接口的返回值
基于上面的Judgecycle接口,接下来我们有两种方法可以求解本题
方法一:
- 假设环中temmet指针与环入口节点的距离为N
- 假设链表头节点与环入口节点的距离为M
- 假设环的总长度(距离)为C
接着我们来分析N,M,C之间存在着什么样的数学关系.
利用前一个题的一个重要结论(见目录):Judgecycle接口中快慢指针相遇时,慢指针在环上走过的距离一定小于环的长度
- 于是:在Judgecycle接口中,快慢指针相遇时慢指针在链表中走过的总距离为(M+C-N)
- 进一步可以得出,快慢指针相遇时快指针在链表中走过的总距离为2*(M+C-N)
- 假设快慢指针相遇时,快指针已经在环中走了n圈,那么我们便可以用另外一种方式表示出快慢指针相遇时快指针在链表中走过的总距离:M+n*C+(C-N)
- 于是得到方程:2*(M+C-N)=M+n*C+(C-N)
- 化简可得:M+C-N = n*C 即:M=(n-1)*C + N (M,C,N,n都为整数)
- 令一个指针temhead初始位置指向链表头节点,另外一个指针temmet初始位置指向环中快慢指针相遇的位置(由Judgecycle接口返回)
- 两个指针同时开始遍历链表,根据关系式M=(n-1)*C + N (M,C,N,n都为整数)可知两个指针必然在链表的入环节点相遇。返回指针的值即可得到答案。
题解代码:
class Solution { public:ListNode* Judgecycle(ListNode* head){if(nullptr==head || nullptr == head->next){return nullptr;}ListNode *fast =head->next->next;ListNode *slow = head->next;while(fast && fast->next && fast!=slow){fast=fast->next->next;slow = slow ->next;}return (fast&&fast->next)? fast : nullptr;//(fast或fast->next为空则表示链表无环)} //(为空说明fast走到表尾) ListNode* detectCycle(ListNode* head){ListNode* temmet = Judgecycle(head); //快慢指针相遇位置节点的地址ListNode* temhead = head;if (temmet) //判断temmet是否为空,为空说明链表不带环{while (temhead != temmet) //两个指针同时向前遍历链表直到相遇{temmet = temmet->next;temhead = temhead->next;}return temmet; //返回相遇位置节点地址}return nullptr; //代表链表无环} };
方法二:
- 确定了Judgecycle接口中快慢指针在环中相遇的位置后,我们在两指针相遇的节点处将环断开
- 于是问题就转换成了求两个相交链表第一个相交节点地址的问题(问题求解参见本期第一个OJ题) ,其中快慢指针在环中相遇位置的节点作为断环后新链表的头节点
因此我们可以调用前两个题的接口来求解本题:
class Solution {ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) //求相交链表第一个交点的接口{ListNode * ptrA = headA;ListNode * ptrB = headB;while(ptrA!=ptrB){ptrA = (ptrA==nullptr)? headB : ptrA->next; //(ptrA==nullptr)代表指针指向A表尾ptrB = (ptrB==nullptr)? headA : ptrB->next; //(ptrB==nullptr)代表指针指向B表尾}return ptrA;} public:ListNode* Judgecycle(ListNode* head) //求快慢指针在环中相遇位置的接口{if(nullptr==head || nullptr == head->next){return nullptr;}ListNode *fast =head->next->next;ListNode *slow = head->next;while(fast && fast->next && fast!=slow){fast=fast->next->next;slow = slow ->next;}return (fast&&fast->next)? fast : nullptr;//(fast或fast->next为空则表示链表无环)} //(为空说明fast走到表尾) ListNode* detectCycle(ListNode* head){ListNode* temmet = Judgecycle(head);if (temmet) //判断temmet是否为空,为空说明链表不带环{ListNode* breakpoint = temmet;while(breakpoint->next != temmet) //找到环中的断开点{breakpoint = breakpoint->next; }breakpoint->next = nullptr; //将环断开return getIntersectionNode(temmet,head);//转化为求两链表第一个交点的问题}return nullptr; //代表链表无环} };
- 根据我们上面各步骤的分析不难得出两种求解方法的时间复杂度都是O(N),但是方法一会比方法二略高效一些。
相关文章:

数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)
目录 一.前言 二.leetcode160. 相交链表 1.问题描述 2.问题分析与求解 三.leetcode141. 环形链表 1.问题描述 2.代码思路 3.证明分析 下一题会用到的重要小结论: 四.leetcode142. 环形链表 II 1.问题描述 2.问题分析与求解 Judgecycle接口…...

数模美赛如何找数据 | 2023年美赛数学建模必备数据库
2023美赛资料分享/思路答疑群:322297051 欧美相关统计数据(一般美赛这里比较多) 1、http://www.census.gov/ 美国统计局(统计调查局或普查局)官方网站 The Census Bureau Web Site provides on-line access to our …...

SSTI漏洞原理及渗透测试
模板引擎(Web开发中) 是为了使 用户界面 和 业务数据(内容)分离而产生的,它可以生成特定格式的文档, 利用模板引擎来生成前端的HTML代码,模板引擎会提供一套生成HTML代码的程序,之后…...

【算法基础】高精度除法
👦个人主页:Weraphael ✍🏻作者简介:目前是C语言 算法学习者 ✈️专栏:【C/C】算法 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬…...

optimizer.zero_grad(), loss.backward(), optimizer.step()的理解及使用
optimizer.zero_grad,loss.backward,optimizer.step用法介绍optimizer.zero_grad():loss.backward():optimizer.step():用法介绍 这三个函数的作用是将梯度归零(optimizer.zero_grad())&#x…...

融资、量产和一栈式布局,这家Tier 1如此备战高阶智驾决赛圈
作者 | Bruce 编辑 | 于婷从早期的ADAS,到高速/城市NOA,智能驾驶的竞争正逐渐升级,这对于车企和供应商的核心技术和产品布局都是一个重要的考验。 部分智驾供应商已经在囤积粮草,响应变化。 2023刚一开年,智能驾驶领域…...

centos7.8安装oralce11g
文章目录环境安装文件准备添加用户操作系统环境配置解压安装问题解决创建用户远程连接为了熟悉rman备份操作,参照大神的博客在centos中安装了一套oracle11g,将安装步骤记录如下环境安装文件准备 这里准备一台centos7.8 虚拟机 配置ip 192.168.18.100 主…...

【蓝桥杯集训·每日一题】AcWing 3956. 截断数组
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维前缀和一、题目 1、原题链接 3956. 截断数组 2、题目描述 给定一个长度为 n 的数组 a1,a2,…,an。 现在,要将该数组从中间截断,得到三个非空子…...

万丈高楼平地起:Linux常用命令
目录 系统管理命令 man命令 ls命令 cd命令 useradd命令 passwd命令 free命令 whoami命令 ps命令 date命令 pwd命令 shutdown命令 文件目录管理命令 touch命令 cat命令 mkdir命令 rm命令 cp命令 mv命令 find命令 more指令 less指令 head指令 tail指令 …...

Linux(Linux的连接使用)
连接Linux我们一般使用CRT或者Xshell工具进行连接使用。 如CRT使用SSH的方式 输出主机,账户,密码那些就可以连接上了。 Linux系统是一个文件型操作系统,有一句话说Linux的一切皆是文件。Linux系统的启动大致有下面几个步骤 Linux系统有7个运…...

Unity中画2D图表(2)——用XChart包绘制散点分布图 + 一条直线方程
散点图用于显示关系。 对于 【相关性】 ,散点图有助于显示两个变量之间线性关系的强度。 对于 【回归】 ,散点图常常会添加拟合线。 举例1:你可以展示【年降雨量】与【玉米亩产量】的关系 举例2:你也可以分析各个【节假日】与【大…...

Go 排序包 sort
写在前面的使用总结: 排序结构体 实现Len,Less,Swap三个函数 package main import ( "fmt" "sort") type StuScore struct { name string score int } type StuScores []StuScore func (s StuScores) Len(…...

Java Email 发HTML邮件工具 采用 freemarker模板引擎渲染
Java Email 发HTML邮件工具 采用 freemarker模板引擎 1.常用方式对比 Java发送邮件有很多的实现方式 第一种:Java 原生发邮件mail.jar和activation.jar <!-- https://mvnrepository.com/artifact/javax.mail/mail --> <dependency><groupId>jav…...

CNI 网络流量分析(六)Calico 介绍与原理(二)
文章目录CNI 网络流量分析(六)Calico 介绍与原理(二)CNIIPAM指定 IP指定非 IPAM IPCNI 网络流量分析(六)Calico 介绍与原理(二) CNI 支持多种 datapath,默认是 linuxDa…...

短视频标题的几种类型和闭坑注意事项
目录 短视频标题的几种类型 1、悬念式 2、蹭热门式 3、干货式 4、对比式方法 5、总分/分总式方法 6、挑战式方式 7、启发激励式 8、讲故事式 02注意事项 1、避免使用冷门、生僻词汇 标题是点睛之笔,核心是视频内容 短视频标题的几种类型 1、悬念式 通过…...

操作系统——1.操作系统的概念、定义和目标
目录 1.概念 1.1 操作系统的种类 1.2电脑的组成 1.3电脑组成的介绍 1.4操作系统的概念(定义) 2.操作系统的功能和目标 2.1概述 2.2 操作系统作为系统资源的管理者 2.3 操作系统作为用户和计算机硬件间的接口 2.3.1用户接口的解释 2.3.2 GUI 2.3.3接…...

【html弹框拖拽和div拖拽功能】原生html页面引入vue语法后通过自定义指令简单实现div和弹框拖拽功能
前言 这是html版本的。只是引用了vue的语法。 这是很多公司会出现的一种情况,就是原生的页面,引入vue的语法开发 这就导致有些vue上很简单的功能。放到这里需要转换一下 以前写过一个vue版本的帖子,现在再加一个html版本的。 另一个vue版本…...

2023新华为OD机试题 - 计算网络信号(JavaScript) | 刷完必过
计算网络信号 题目 网络信号经过传递会逐层衰减,且遇到阻隔物无法直接穿透,在此情况下需要计算某个位置的网络信号值。 注意:网络信号可以绕过阻隔物 array[m][n] 的二维数组代表网格地图,array[i][j] = 0代表 i 行 j 列是空旷位置;array[i][j] = x(x 为正整数)代表 i 行 …...

27.边缘系统的架构
文章目录27 Architecures for the Edge 边缘系统的架构27.1 The Ecosystem of Edge-Dominant Systems 边缘主导系统的生态系统27.2 Changes to the Software Development Life Cycle 软件开发生命周期的变化27.3 Implications for Architecture 对架构的影响27.4 Implications …...

机器学习强基计划8-1:图解主成分分析PCA算法(附Python实现)
目录0 写在前面1 为什么要降维?2 主成分分析原理3 PCA与SVD的联系4 Python实现0 写在前面 机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理;“广”在分析多个机器学习模型…...

Hudi-集成Spark之spark-shell 方式
Hudi集成Spark之spark-shell 方式 启动 spark-shell (1)启动命令 #针对Spark 3.2 spark-shell \--conf spark.serializerorg.apache.spark.serializer.KryoSerializer \--conf spark.sql.catalog.spark_catalogorg.apache.spark.sql.hudi.catalog.Hoo…...

Python爬虫:从js逆向了解西瓜视频的下载链接的生成
前言 最近花费了几天时间,想获取西瓜视频这个平台上某个视频的下载链接,运用js逆向进行获取。其实,如果小编一开始就注意到这一点(就是在做js逆向时,打了断点之后,然后执行相关代码,查看相关变量的值,结果一下子就蹦出很多视频相关的数据,查看了网站下的相关api链接,也…...

Numpy-如何对数组进行切割
前言 本文是该专栏的第24篇,后面会持续分享python的数据分析知识,记得关注。 继上篇文章,详细介绍了使用numpy对数组进行叠加。本文再详细来介绍,使用numpy如何对数组进行切割。说句题外话,前面有重点介绍numpy的各个知识点。 感兴趣的同学,可查看笔者之前写的详细内容…...

Python之字符串精讲(下)
前言 今天继续讲解字符串下半部分,内容包括字符串的检索、大小写转换、去除字符串中空格和特殊字符。 一、检索字符串 在Python中,字符串对象提供了很多用于字符串查找的方法,主要给大家介绍以下几种方法。 1. count() 方法 count() 方法…...

Python图像卡通化animegan2-pytorch实例演示
先看下效果图: 左边是原图,右边是处理后的图片,使用的 face_paint_512_v2 模型。 项目获取: animegan2-pytorch 下载解压后 cmd 可进入项目地址的命令界面。 其中 img 是我自己建的,用于存放图片。 需要 torch 版本 …...

谢希仁版《计算机网络》期末总复习【完结】
文章目录说明第一章 计算机网络概述计算机网络和互联网网络边缘网络核心分组交换网的性能网络体系结构控制平面和数据平面第二章 IP地址分类编址子网划分无分类编址特殊用途的IP地址IP地址规划和分配第三章 应用层应用层协议原理万维网【URL / HTML / HTTP】域名系统DNS动态主机…...

问:React的useState和setState到底是同步还是异步呢?
先来思考一个老生常谈的问题,setState是同步还是异步? 再深入思考一下,useState是同步还是异步呢? 我们来写几个 demo 试验一下。 先看 useState 同步和异步情况下,连续执行两个 useState 示例 function Component() {const…...

深度理解机器学习16-门控循环单元
评估简单循环神经网络的缺点。 描述门控循环单元(Gated Recurrent Unit,GRU)的架构。 使用GRU进行情绪分析。 将GRU应用于文本生成。 基本RNN通常由输入层、输出层和几个互连的隐藏层组成。最简单的RNN有一个缺点,那就是它们不…...

Python中Generators教程
要想创建一个iterator,必须实现一个有__iter__()和__next__()方法的类,类要能够跟踪内部状态并且在没有元素返回的时候引发StopIteration异常. 这个过程很繁琐而且违反直觉.Generator能够解决这个问题. python generator是一个简单的创建iterator的途径…...

数据结构与算法基础-学习-10-线性表之栈的清理、销毁、压栈、弹栈
一、函数实现1、ClearSqStack(1)用途清理栈的空间。只需要栈顶指针和栈底指针相等,就说明栈已经清空,后续新入栈的数据可以直接覆盖,不用实际清理数据,提升了清理效率。(2)源码Statu…...