【初阶数据结构】——leetcode:160. 相交链表
文章目录
- 1. 题目介绍
- 2. 思路1:暴力求解
- 算法思想
- 代码实现
- 3. 思路2:快慢指针
- 算法思想
- 代码实现
1. 题目介绍
链接: link
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
2. 思路1:暴力求解
算法思想
首先第一种思路就是暴力求解,这可能是我们最容易想到的:
让A链表的每个结点依次与B中所有结点逐个比较(拿B的跟A比也是一样),当然这里要注意比较的时候应该比较结点的地址,而不应该比较结点的值。结点的值一样并不能证明它们相交。
这种方法思想很简单,但是效率不好,这样的话时间复杂度就是O(N^2)
代码实现
代码也很简单,可以给大家写一下:
也可以通过。
//暴力求解,让A链表的每个结点依次与B中所有结点逐个比较。O(N^2)
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{struct ListNode* curA = headA;struct ListNode* curB = headB;while (curA){curB=headB;while (curB){if (curA == curB)return curA;curB = curB->next;}curA = curA->next;}return NULL;
}
但是上面的算法效率不是很好,我们能不能优化一下呢?
3. 思路2:快慢指针
算法思想
大家思考一个问题:
上面我们暴力比对结点的地址来寻找链表的交点。
但是为什么要拿A链表的每个结点依次与B中所有结点逐个比较呢?
为什么不能同步的遍历两个链表,比较对应的结点呢?
如果同步遍历话,就是O(N)
了
🆗,不能直接这样,因为两个链表的长度可能是不一样的。
比如像这样
如果我们同步的遍历去比对,显然是不行的,不能得到正确的结果。
那不能直接同步遍历两个链表的去比较,我们能不能想个办法让他们可以同步遍历去比较呢?
我们来分析一下。
如果两个链表相交,但是长度不相等,那么不相等的部分一定是在交点之前的。
因为相交之后它们后面的结点都是一样的嘛。
那上面我们分析了,就是因为两个链表的长度可能不一样,所以不能同步遍历去比较。
那我们能不能把他们变成一样长呢?
🆗,我们可以这样做
我们可以同步遍历去比较。
但是,如果长度不相等,我们要先让较长的那个链表的遍历指针先走长度的差值步
此时,我们看到,是不是就可以让curA和curB同时往后走,比较对应的结点了。
这样如果它们有交点的话,就一定会出现curA==curB,此时这两个指针指向的结点就是第一个交点,返回curA或curB都可。
如果没有交点,那就一直往后走curA不会和curB相等,遍历结束,curA和curB都走到空,返回curA或curB都可。(当然待会大家看我们的代码,不相交的话我们在求长度差值的时候其实就能判断出来了)
所以:
我们可以先遍历一遍两个链表,求出它们的长度,判断出谁长谁短,并计算出长度的差值。
然后让长的链表先走差值步,再同步往后走,比较对应结点,找交点。
代码实现
理清了思路,我们来写一下代码:
提交一下:
过啦!
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA=headA;struct ListNode *curB=headB;int lenA=0;int lenB=0;//找尾,先判断是否相交,不相交直接返回NULL,相交再找while(curA->next){lenA++;curA=curA->next;}//计算准确长度应该这样写:while(curA)//这样while(curA->next)比实际长度小1,但是两个都小1,不影响差值//而这样写循环结束cur就是尾,可直接判断是否相交while(curB->next){lenB++;curB=curB->next;}//尾不相等,则不相交if(curA!=curB)return NULL;//计算差值int gap=abs(lenA-lenB);//找出长的那一个struct ListNode *longlist=headA;struct ListNode *shortlist=headB;if(lenB>lenA){longlist=headB;shortlist=headA;}//长表先走差值步while(gap--){longlist=longlist->next;}//再一起走,比较两个链表的当前结点是否相同//,第一个相同的就是第一个交点while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}
相关文章:

【初阶数据结构】——leetcode:160. 相交链表
文章目录 1. 题目介绍2. 思路1:暴力求解算法思想代码实现 3. 思路2:快慢指针算法思想代码实现 1. 题目介绍 链接: link 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&…...
【Go】goroutine并发常见的变量覆盖案例
越过山丘 遇见六十岁的我 拄着一根白手杖 在听鸟儿歌唱 我问他幸福与否 他笑着摆了摆手 在他身边围绕着一群 当年流放归来的朋友 他说你不必挽留 爱是一个人的等候 等到房顶开出了花 这里就是天下 总有人幸福白头 总有人哭着分手 无论相遇还是不相遇 都是献给岁月的序曲 …...

基于SSM+Jsp+Mysql的快递管理系统
开发语言:Java框架:ssm技术:JSPJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包…...
如何动态往Spring容器注册/移除bean?
几个关键点需要知道 本文不谈原理,直接上实战。 几个关键点:如何拿到Spring上下文来创建bean或移除bean?如何准备构建bean所需的BeanDefinition? 第一问:可注入bean工厂org.springframework.beans.factory.support.…...

C语言交换二进制位的奇数偶数位
基本思路 我们要先把想要交换的数的二进制位给写出来假如交换13的二进制位,13的二进制位是 0000 0000 0000 0000 0000 0000 0000 1101然后写出偶数位的二进制数(偶数位是1的) 1010 1010 1010 1010 1010 1010 1010 1010然后写出奇数位的二进…...

爬虫实战三、PyCharm搭建Scrapy开发调试环境
#一、环境准备 Python开发环境以及Scrapy框架安装,参考:爬虫实战一、Scrapy开发环境(Win10Anaconda)搭建 PyCharm安装和破解,参考:爬虫实战二、2019年PyCharm安装(激活到2100年) …...

2012年认证杯SPSSPRO杯数学建模C题(第一阶段)碎片化趋势下的奥运会商业模式全过程文档及程序
2012年认证杯SPSSPRO杯数学建模 C题 碎片化趋势下的奥运会商业模式 原题再现: 从 1984 年的美国洛杉矶奥运会开始,奥运会就不在成为一个“非卖品”,它在向观众诠释更高更快更强的体育精神的同时,也在攫取着巨大的商业价值&#…...
【Next.js】连接 MongoDB 实现基本的接口
【Next.js】连接 MongoDB 实现基本的接口 什么是 MongoDB MongoDB 是由C语言编写的,是一个基于分布式文件存储的开源数据库系统。在高负载的情况下,添加更多的节点,可以保证服务器性能。MongoDB 旨在为WEB应用提供可扩展的高性能数据存储解…...
中值滤波算法与SSE2指令集并行优化
中值滤波算法是经典图像处理中极为常见的操作,一般我们通过调用OpenCV或者是Matlab直接进行使用,以至于有种它本来就很容易实现且速度很快的错觉。近来用到中值滤波算法,因为不想用到OpenCV库或者Matlab而对其实现研究了一番,才发现其中有很多值得注意的细节。下面我们结合…...

2012年认证杯SPSSPRO杯数学建模B题(第二阶段)节能减排全过程文档及程序
2012年认证杯SPSSPRO杯数学建模 节能减排、抑制全球气候变暖 B题 白屋顶计划 原题再现: 第二阶段问题 虽然环境学家对地球环境温度的改变有许多种不同观点,但大多数科学家可以达成一个基本的共识:近年来人类的活动,尤指二氧…...
NOI - OpenJudge - 2.5基本算法之搜索 - 2753:走迷宫 - 超级无敌详细题解(含多个不同算法AC代码)
点赞关注吧~ 2753:走迷宫 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最…...

什么是Redis数据一致性?如何解决?
在系统中缓存最常用的策略是:服务端需要同时维护DB和cache,并且是以DB的结果为准–Cache-Aside Pattern(缓存分离模式、旁路缓存) 读数据 单纯的读数据是不会产生数据不一致,只有并发下读和写才会存在数据不一致。 写…...
【办公软件】开发常用网站
文章目录 一、开发社区二、开发学习三、视图工具四、开发工具五、前端web开发工具六、开发接口官网 备用产看。 https://www.webhub123.com https://www.webhub123.com/#/home/detail?projectHashid59183272&ownerUserid22053727 java全栈只是体系:https://www…...

车道线检测_Canny算子边缘检测_1
Canny算子边缘检测(原理) Canny算子边缘检测是一种经典的图像处理算法,由John F. Canny于1986年提出,用于精确、可靠地检测数字图像中的边缘特征。该算法设计时考虑了三个关键目标:低错误率(即尽可能多地检…...

kubadm部署kubernetes
什么是kubernetes Kubernetes是一款应用于集群的,容器自动部署、扩展和管理的开源平台,提供了一种以容器为中心的基础架构。利用kubernetes,你可以快速高效地响应客户如下请求: 应用程序的动态、精准部署应用程序的动态扩展无缝推…...
Sqlite插入单引号和双引号,防止sql注入
1. 方法1 sqlite3_mprintf替换sprintf,%q替换%s. 1.1. 举例 修改前代码 //修改前, hello123写入失败char sql[1000]char* sql sprintf("UPDATE table SET name %s WHERE name_id %d","hello123", 1);rc sqlite3_exec(db, sql, NULL, NULL, &err…...

代码随想录算法训练营第二十九天(回溯5)|491. 非递减子序列、46. 全排列、47. 全排列 II(JAVA)
文章目录 491. 非递减子序列解题思路源码 46. 全排列解题思路源码 47. 全排列 II解题思路源码 总结 491. 非递减子序列 给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 …...

【CANN训练营笔记】AscendCL图片分类应用(C++实现)
样例介绍 基于PyTorch框架的ResNet50模型,对*.jpg图片分类,输出各图片所属分类的编号、名称。 环境介绍 华为云AI1s CPU:Intel Xeon Gold 6278C CPU 2.60GHz 内存:8G NPU:Ascend 310 环境准备 下载驱动 wget ht…...

从头开发一个RISC-V的操作系统(二)RISC-V 指令集架构介绍
文章目录 前提ISA的基本介绍ISA是什么CISC vs RISCISA的宽度 RISC-V指令集RISC-V ISA的命名规范模块化的ISA通用寄存器Hart特权级别内存管理与保护异常和中断 目标:通过这一个系列课程的学习,开发出一个简易的在RISC-V指令集架构上运行的操作系统。 前提…...
uniapp/设置桌面角标/发送系统通知/动态修改桌面应用图标/展示3d模型/仿淘宝二楼
uniapp的安卓apk图标角标设置消息数量 1、主要方法: 设置角标: plus.runtime.setBadgeNumber(999) 清除角标: //plus.runtime.setBadgeNumber(0)//没有效果 plus.runtime.setBadgeNumber(-1) //有效果 2、使用在具体的生命周期 1、打开app获取…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...

麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...