【数据结构OJ题】相交链表
原题链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述

2. 思路分析
看到这道题,很容易想到的方法就是暴力求解,就是将一个链表的每个结点的地址分别和另外一个链表的每个结点的地址进行比较,如果有相等的,就说明相交了。(注意这里不能比值,因为两个不同的结点值有可能一样)。但是这样的时间复杂度太高了,为O(N^2)。
这道题有一个很好的做法:
先计算出两个链表的长度,让长的链表先走相差的长度,然后两个链表同时走,直到遇到相同的结点,即为第一个公共结点。
我们定义了四个变量curA,curB,lenA,lenB。
我们用结构体指针curA遍历链表A,用结构体指针curB遍历链表B。
lenA表示链表A的长度,lenB表示链表B的长度。
用while循环通过遍历分别得到了链表A和B的长度。
我们判断尾结点是否相等,如果尾结点相等,说明两个链表一定相交!!!
(我们看下图,如果两个链表相交,那么从这个相交的结点(包括这个交点)之后的结点,在两个链表中都是相等的。所以尾结点相等,说明两个链表一定相交。)

如果两个链表不相交(curA!=curB),我们直接返回空指针NULL。
如果两个链表相交,我们先让长的链表走两个链表长度的差距步(gap)。因为不知道两个链表哪个长,所以我们使用了abs()函数,差距步gap就是abs(lenA-lenB)。
之后我们又引入了两个结构体指针longList和shortList分别指向长链表和短链表的头。这里用了if语句判断,先假设某个链表是长链表,如果不是,就让它等于短链表。
然后我们用一个while循环让长链表走差距步(while(gap--))。

然后让longList和shortList这两个结构体指针同时走,找交点,找到交点时结束循环。
最后返回longList即可。
3. 代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA=headA,*curB=headB;int lenA=1,lenB=1;//计算链表长度while(curA->next){curA=curA->next; ++lenA;}while(curB->next){curB=curB->next;++lenB;}//不相交if(curA!=curB)return NULL;int gap=abs(lenA-lenB);struct ListNode *longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}//长的先走差距步while(gap--){longList=longList->next;}//同时走找交点while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}

相关文章:
【数据结构OJ题】相交链表
原题链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 看到这道题,很容易想到的方法就是暴力求解,就是将一个链表的每个结点的地址…...
【华为OD机试】最小传输时延I【2023 B卷|200分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 某通信网络中有N个网络结点,用1到N进行标识。网络通过一个有向无环图表示, 其中图的边的值表示结点之间的消息传递时延。 现给定相连节点之间的时延列表times[i]={u,v,w},其中u表示…...
Android13 网络 Adb 默认开启
Android 13 网络 Adb 默认开启 文章目录 Android 13 网络 Adb 默认开启一、前言二、默认adb 代码实现1、修改的目录:2、具体修改:(1)在XXX_device.mk 添加属性(2)设置固定端口号(3)去…...
Git分享-规范/建议/技巧
1. Git多人协作开发流程图 1.1 processOn默认的模板 1.2 改造之后 https://www.processon.com/view/link/64ccaf56a433c931b2f9428a 访问密码:512I ① 总流程图 ② feat分支(功能/需求 分支)流程 ③ bugfix分支(紧急补丁分支&…...
vue3文件下载功能
定义方法: utils.js /**** param url 目标下载接口* param query 查询参数* param fileName 文件名称* returns {*}*/ export function downBlobFile(url: any, query: any, fileName: string) {return request({//url: url,method: get,responseType: blob,param…...
Python调用文心一言的API
最近申请了文心一言的key,然后尝试调用了一下文心一言,这里使用一个简单的方式来调用文心一言: pip install paddle-pipelinesfrom pipelines.nodes import ErnieBotapi_key "your apply key" secret_key "your apply secr…...
【计算机网络八股】计算机网络(一)
目录 计算机网络的各层协议及作用?TCP和UDP的区别?UDP 和 TCP 对应的应用场景是什么?详细介绍一下 TCP 的三次握手机制?为什么需要三次握手,而不是两次?为什么要三次握手,而不是四次?…...
记录一次arcgis engine开发版本引入问题
之前基于arcigs 10.1vs2013开发的程序,现在拿出来要改,但是目前版本是arcgis10.7vs2017/vs2019,打开后无论如何替换引用版本,都报错 (具体版本对应可以看这:ArcGIS Engine 与 Visual Studio 版本对照表_vs2019对应啥版…...
2023年Java毕业设计怎样选题,有哪些注意事项,300道Java毕业设计题目
文章目录 一、确定个人兴趣和技能二、考虑实际应用价值三、注重创新和独特性四、合理规划时间和资源五、注重实践和测试Java 毕业设计题目参考第一部分第二部分 小结 随着计算机技术的不断发展,Java编程语言已经成为了众多大学计算机专业学生必修的一门课程。而Java…...
算法-滑动窗口-串联所有单词的子串
算法-滑动窗口-串联所有单词的子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/ 1.2 题目描述 2 滑动窗口Hash表 2.1 解题思路 构建一个大小为串联子串的总长的滑动窗口为每个words中的子串创建一个hash表, <子…...
2023年7月京东美妆护肤品小样行业数据分析(京东数据挖掘)
如今,消费者更加谨慎,消费决策也更加理性。在这一消费环境下,美妆护肤市场中,面对动辄几百上千的化妆品,小样或体验装无疑能够降低消费者的试错成本。由此,这门生意也一直备受关注。 并且,小样…...
记录Taro巨坑,找不到sass类型定义文件
问题 taronutuisassts项目里tsconfig.json一直报红报错。 找不到“sass”的类型定义文件。 程序包含该文件是因为: 隐式类型库 “sass” 的入口点 其实正常人想的肯定是装上 types/sass试试。开始我试过了,没用。删了依赖重装也没用。后面在issue中找到答案了 解决…...
CS1988|C#无法在异步方法中使用ref,in,out类型的参数的问题
CS1988|C#无法在异步方法中使用ref,in,out类型的参数 🌀|场景: BlazorServer的场景中推荐使用异步方法,使用ref,out,in为参数前缀则报错CS1988 原因如下: ref parameters are not supported in async methods because the method may not h…...
ubuntu开机失败——ACPI Error
开机循环进入GNU GRUB 或者 黑屏 1.acpioff 解决办法 1)先用下面方法进入系统 2)更改grub ref 开机循环进入GNU GRUB 或者 黑屏 有提示ACPI Error错误如图: 解决办法 1)先用下面方法进入系统 在GUN GRUB界面,选择ubun…...
搭建开发环境-操作系统篇(一键搭建开发环境)
概述 所谓工欲善其事必先利其器,搭环境往往是开发过程中卡出很多初学者的拦路虎。 对于很多老鸟来说,很多东西都已经习惯成自然,也就没有刻意和初学者说。但对于很多初学者,却是受益良多。 这个系列,先从操作系统开始…...
人工智能AI绘画接入使用文档
人工智能AI绘画接入使用 一、人工智能AI绘画二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 AI绘画优秀描述例子四、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 五、重要说明六、AI绘画成果展示 一、人工智能AI绘画 AI作画,用户可以在平台上…...
如何使用PyQt进行文件操作
PyQt是一个非常强大的Python GUI库,它可以帮助我们创建漂亮的跨平台应用程序。不过,在你开始使用PyQt进行文件操作之前,我想提醒你,这并不是在操作文件系统,而是在操作文件和文件夹。 首先,我们要导入PyQt…...
阿里云CDN加速器基本概念与购买开通
文章目录 1.CDN加速器的基本概念1.1.CDN加速器基本介绍1.2.网站引入CDN加速器的架构图1.3.CDN加速器的工作原理1.4.引入CDN后域名解析变成了CNAME? 2.开通阿里云CDN加速服务 1.CDN加速器的基本概念 CDN加速器官方文档:https://help.aliyun.com/product/…...
2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C
2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C https://ac.nowcoder.com/acm/contest/63602/F 文章目录 2023河南萌新联赛第(六)场:河南理工大学-F 爱睡大觉的小C题意解题思路 题意 新学期的概…...
[C++ 网络协议编程] 域名及网络地址
1. DNS服务器 DNS(Domain Name System):是对IP地址和域名(如:www.baidu.com等)进行相互转换的系统,其核心是DNS服务器。 我们输入的www.baidu.com是域名,是一种虚拟地址,而非实际地…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
【Java】Ajax 技术详解
文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...
6.9本日总结
一、英语 复习默写list11list18,订正07年第3篇阅读 二、数学 学习线代第一讲,写15讲课后题 三、408 学习计组第二章,写计组习题 四、总结 明天结束线代第一章和计组第二章 五、明日计划 英语:复习l默写sit12list17&#…...
【大厂机试题解法笔记】矩阵匹配
题目 从一个 N * M(N ≤ M)的矩阵中选出 N 个数,任意两个数字不能在同一行或同一列,求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求:1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...
