【链表OJ】相交链表 环形链表1
前言:
💥🎈个人主页:Dream_Chaser~ 🎈💥
✨✨刷题专栏:http://t.csdn.cn/UlvTc
⛳⛳本篇内容:力扣上链表OJ题目
目录
一.leetcode 160. 相交链表
1.问题描述:
2.解题思路:
二.leetcode 141.环形链表
1.问题描述:
2.代码思路:
3.问题证明:
一.leetcode 160. 相交链表
来源:160. 相交链表 - 力扣(LeetCode)
1.问题描述:
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回NULL 。
图示两个链表在节点c1开始相交:
已知a1与b1的头结点地址,并分别用headA和headB指针指向
- 题目数据 保证 整个链式结构中不存在环。
- 注意,函数返回结果后,链表必须 保持其原始结构 。
题目接口:
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{}
2.解题思路:
原始链表:
- 首先定义tailA和tailB分别遍历a链表和b链表,在遍历过程中,分别求出两链表长度,分别定义为lenA和lenB,然后用lenA和lenB相减取差的绝对值,计为差距步gap
- 然后定义指向长链表的指针longList,和指向短链表的指针shortList,用前面定义的LenA和LenB比较它们的长度,进行合适赋值,接着让长的链表走差距步gap。若长链表结点的地址不等于短链表,则让tailA和tailB指针继续走,有相等结点则跳出循环,返回此时的longList或者shortList。
实现代码:
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1, lenB = 1;//原始长度定义为1才是正确的while (tailA){tailA = tailA->next;lenA++;}while (tailB){tailB = tailB->next;lenB++;}if (tailA != tailB)//若两指针到结束也找不到相等结点,则返回NULLreturn NULL;int gap = abs(lenA - lenB);//取出两者相减的绝对值,赋值给gap表示两链表的差距步struct ListNode*longList = headA;//先假定A链表为长链表struct ListNode* shortList = headB;if (lenA < lenB)//接着两链表比较,如果满足此条件,则重新赋值,定义B链表的为长链表{longList = headB;shortList = headA;}while (gap--)//长链表先走差距步{longList = longList->next;}while (longList != shortList)//若没有相等(地址相等)则继续遍历{longList = longList->next;shortList = shortList->next;}return shortList; }代码执行:
二.leetcode 141.环形链表
1.问题描述:
给你一个链表的头节点
head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪
next指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回
true。 否则,返回false。
题解接口:
bool hasCycle(struct ListNode *head) {}
2.代码思路:
本题的代码思路:
定义一个快指针,让其先走两步,接着定义一个慢指针,一次走一步,反复此循环。
- 如果快慢指针指向的地址相等,则证明链表中存在环。
- 如果快指针提前指向NULL,循环结束,则证明不是环形链表,直接返回false。
函数实现
bool hasCycle(struct ListNode *head) {struct ListNode* fast=head,*slow =head;while(fast && fast->next){fast=fast->next->next;//快指针先走两步,慢指针走一步slow=slow->next; //慢指针走一步if(fast==slow)//指针相遇表明链表带环{return true;}}return false;//否则返回NULL }代码执行:
然而本题的重点在于如何证明上面的代码的实现逻辑,是一个数学问题。
3.问题证明:
1、slow和fast一定会相遇吗?
答:一定会
画一张图来证明一下, 此时两指针同时指向头节点的地址。
接着先让快指针fast=fast->next->next(快指针先走两步),后让 slow=slow->next(慢指针走一步).
fast会先进环,slow会后进环,假设slow进环时,slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走2步,他们之间距离缩小1。
2、slow走1步,fast走n(3/4/5….)步可以吗?(n > 2)
不一定
举例:
slow每次走一步,fast每次走三步,它们一定可以相遇吗?答:不一定。
画图
当快慢指针之间的距离个数为奇数时
fast会先进环,slow会后进环,假设slow进环时, slow和fast之间的距离为N
slow进环以后,fast开始追击slow,slow每走1步,fast每走3步,他们之间距离缩小2
当快指针追赶上慢指针时,此时错过了,并进入新一轮的追击,假设一个值C为环的长度,那么快慢指针的距离此时必为C-1
所以,如果C-1是奇数那么fast永远追不上slow
当C-1的距离为偶数时,那么此时的距离变化为
N N-2 N-4 ... 4 2 0 ,0则表示此时两指针相遇,表明下一轮可以追上。
本文结束,如有错误,我会继续更新关于链表oj的题目,欢迎大家指正!
相关文章:
【链表OJ】相交链表 环形链表1
前言: 💥🎈个人主页:Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 一.leetcode 160. 相交链表 1.问题描述: 2.解题思路: 二.leetcode 141.环形链表 …...
DevOps之自动化测试
什么是自动化测试? 明确一下自动化测试不是什么。自动化测试不是指自动化生成测试代码,而是自动化地执行由开发人员或测试人员编写的测试代码。正如下面这句谚语:“绝不要手工去做任何可以被自动化处理的事情。——Curt Hibbs” 之前是由人…...
Java 程序打印 OpenCV 的版本
我们可以使用 Java 程序来使用 OpenCV。 OpenCV 的使用需要动态库的加载才可以。 加载动态库 到 OpenCV 的官方网站上下载最新的发布版本。 Windows 下载的是一个可执行文件,没关系,这个可执行文件是一个自解压程序。 当你运行以后会提示你进行解压。…...
ChatGPT⼊门到精通(2):ChatGPT 能为我们做什么
⼀、雇佣免费的⼲活⼩弟 有了ChatGPT后,就好⽐你有了好⼏个帮你免费打⼯的「⼩弟」,他们可以帮你做很多 ⼯作。我简单总结⼀些我⽬前使⽤过的⽐较好的基于ChatGPT的服务和应⽤。 1、总结、分析 当我们在阅读⼀些⽂章和新闻的时候,有的⽂章写…...
线程和进程的区别是什么?
线程(Thread)和进程(Process)是操作系统中两个重要的概念,用于管理程序的执行。它们有以下区别: 定义:进程:进程是程序的一个执行实例,它包含了程序的代码、数据以及执行上下文。进程是操作系统分配资源和调度的基本单位。线程:线程是进程的子执行单元,一个进程可以…...
力扣27.移除元素
27. 移除元素 提示 简单 1.9K 相关企业 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序…...
指针(个人学习笔记黑马学习)
1、指针的定义和使用 #include <iostream> using namespace std;int main() {int a 10;int* p;p &a;cout << "a的地址为:" << &a << endl;cout << "a的地址为:" << p << endl;…...
vue 路由动态加载
在 Vue.js 中,可以使用 webpack 的动态导入语法来实现路由动态加载。下面是一个简单的示例: const Home () > import(/* webpackChunkName: "home" */ ./views/Home.vue); const About () > import(/* webpackChunkName: "about…...
电脑识别不了固态硬盘怎么办?
在使用固态硬盘时,可能会出现电脑无法识别的情况,这时我们就无法使用固态硬盘中的数据。那么,电脑识别不了固态硬盘怎么办? 为什么电脑识别不了固态硬盘? 一般来说,电脑识别不了固态硬盘是因为以下3个原因…...
QCustomPlot 绘制卡顿问题
大数据量导致曲线绘制卡顿问题 这里提供一个思路在跟踪源码中发现底层卡顿在vector的resize() 此处扩容中 所以尽量使用下面的接口 /*! \overloadAdds the provided data point as \a key and \a value to the current data.Alternatively, you can also access and modify t…...
uni-app开发小程序,radio单选按钮,点击可以选中,再次点击可以取消
一、实现效果: 二、代码实现: 不适用官方的change方法,自己定义点击方法。 动态判断定义的值是否等于遍历的值进行回显,如果和上一次点击的值一样,就把定义的值改为null <template><view><radio-group&…...
【Qt专栏】实现单例程序,禁止程序多开的几种方式
目录 一,简要介绍 二,实现示例(Windows) 1.使用系统级别的互斥机制 2.通过共享内存(进程间通信-IPC) 3.使用命名互斥锁(不推荐) 4.使用文件锁 5.通过网络端口检测 一…...
力扣26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做…...
【机器学习】鸢尾花分类-逻辑回归示例
这段代码是一个完整的示例,展示了如何使用逻辑回归对鸢尾花数据集进行训练、保存模型,并允许用户输入数据进行预测。以下是对这段代码的总结:功能: 这段代码演示了如何使用逻辑回归对鸢尾花数据集进行训练,并将训练好的…...
Flink CDC介绍
1.CDC概述 CDC(Change Data Capture)是一种用于捕获和处理数据源中的变化的技术。它允许实时地监视数据库或数据流中发生的数据变动,并将这些变动抽取出来,以便进行进一步的处理和分析。 传统上,数据源的变化通常通过…...
Java集合sort排序报错UnsupportedOperationException处理
文章目录 报错场景排查解决UnmodifiableList类介绍 报错场景 我们使用的是PostgreSQL数据库,存储业务数据,业务代码使用的是Spring JPA我们做的是智慧交通信控平台,有个功能是查询展示区域的交通态势,需要按照不同维度排序展示区…...
安防监控/磁盘阵列存储/视频汇聚平台EasyCVR调用rtsp地址返回的IP不正确是什么原因?
安防监控/云存储/磁盘阵列存储/视频汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等,能对外分发RTSP、RT…...
Spring boot开启定时任务
Cron表达式生成器 基于接口的方式 使用Scheduled 注解很方便,但缺点是当我们调整了执行周期的时候,需要重启应用才能生效,这多少有些不方便。为了达到实时生效的效果,那么可以使用接口来完成定时任务,统一将定时器信…...
package.json相关知识记录
一、相关字段 npm官方字段介绍 🍧 bin > 简单理解:指定命令的名称及路径 🍉 相当于想path中添加路径,局部安装是在./node_modules/.bin/,全局安装是在全局的bin目录 🍉 bin指定的文件必须…...
VueRouter使用详解(5000字通关大全)
Vue Router是一个官方的路由管理器,它可以让我们在Vue应用中实现单页面应用(SPA)的效果,即通过改变URL而不刷新页面来显示不同的内容。Vue Router可以让我们定义多个路由,每个路由对应一个组件,当URL匹配到…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...











