【LeetCode】160. 相交链表
160. 相交链表
难度:简单
题目
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal- 相交的起始节点的值。如果不存在相交节点,这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中(从头节点开始)跳到交叉节点的节点数skipB- 在listB中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
示例 2:
输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。
提示:
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点,intersectVal为0 - 如果
listA和listB有交点,intersectVal == listA[skipA] == listB[skipB]
**进阶:**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?
个人题解
也可考虑将一条链用 HashSet 存储判断
方法一:栈
用栈存储一条链,通过栈从后往前遍历栈同时每次都遍历另一条链比对,直到不相等时返回。
时间复杂度O(m * n)
空间复杂度O(m)
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Deque<ListNode> stack = new LinkedList<>();ListNode ans = headA;while (ans != null) {stack.push(ans);ans = ans.next;}while (!stack.isEmpty()) {ListNode pop = stack.pop();ListNode other = headB;while (other != null) {if (other == pop) {break;}other = other.next;}if (other == null) {break;}ans = other;}return ans;}
}
参考题解
根据题目意思 如果两个链表相交,那么相交点之后的长度是相同的
我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此,我们必须消除两个链表的长度差
- 指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历
- 如果 pA 到了末尾,则 pA = headB 继续遍历
- 如果 pB 到了末尾,则 pB = headA 继续遍历
- 比较长的链表指针指向较短链表head时,长度差就消除了
- 如此,只需要将最短链表遍历两次即可找到位置
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;
}
作者:房建斌学算法
链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/10774/tu-jie-xiang-jiao-lian-biao-by-user7208t/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章:
【LeetCode】160. 相交链表
160. 相交链表 难度:简单 题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中…...
数据集笔记:NGSIM (next generation simulation)
1 数据集介绍 数据介绍s Next Generation Simulation (NGSIM) Open Data (transportation.gov) 数据地址:Next Generation Simulation (NGSIM) Vehicle Trajectories and Supporting Data | Department of Transportation - Data Portal 时间2005年到2006年间地…...
解决docker运行elastic服务端启动不成功
现象: 然后查看docker日志,发现有vm.max_map_count报错 ERROR: [1] bootstrap checks failed [1]: max virtual memory areas vm.max_map_count [65530] is too low, increase to at least [262144] 解决办法: 1. 宿主机(运行doc…...
mysql数据库中mysql database 数据被破坏产生的一系列问题
在执行sql脚本时,没有注意到sql脚本文件包含了对mysql 原始数据库的操作,执行了脚本。 脚本执行成功之后,登录或链接数据库查看数据时报错: The user specified as a definer (‘mysql.infoschema’‘localhost’) does not exis…...
基于变形卷积和注意机制的带钢表面缺陷快速检测网络DCAM-Net(论文阅读笔记)
原论文链接->DCAM-Net: A Rapid Detection Network for Strip Steel Surface Defects Based on Deformable Convolution and Attention Mechanism | IEEE Journals & Magazine | IEEE Xplore DCAM-Net: A Rapid Detection Network for Strip Steel Surface Defects Base…...
05-Spring Boot工程中简化开发的方式Lombok和dev-tools
简化开发的方式Lombok和dev-tools Lombok常用注解 Lombok用标签方式代替构造器、getter/setter、toString()等重复代码, 在程序编译的时候自动生成这些代码 注解名功能NoArgsConstructor生成无参构造方法AllArgsConstructor生产含所有属性的有参构造方法,如果不希望含所有属…...
AIGC 技术在淘淘秀场景的探索与实践
本文介绍了AIGC相关领域的爆发式增长,并探讨了淘宝秀秀(AI买家秀)的设计思路和技术方案。文章涵盖了图像生成、仿真形象生成和换背景方案,以及模型流程串联等关键技术。 文章还介绍了淘淘秀的使用流程和遇到的问题及处理方法。最后,文章展望…...
ANSYS网格无关性检查
网格精度对应力结果存在很大的影响,有时候可以发现,随着网格精度逐渐提高,所求得的最大应力值逐渐趋于收敛。 默认网格: 从默认网格下计算出的应力云图可以发现,出现了的三处应力奇异点,此时算出的应力值是…...
设计模式-责任链-笔记
动机(Motivation) 在软件构建过程中,一个请求可能被多个对象处理,但是每个请求在运行时只能有个接受者,如果显示指定,将必不可少地带来请求者与接受者的紧耦合。 如何使请求的发送者不需要指定具体的接受…...
SpringMvc请求原理流程
springmvc是用户和服务沟通的桥梁,官网提供了springmvc的全面使用和解释:DispatcherServlet :: Spring Framework 流程 1.Tomcat启动 2.解析web.xml文件,根据servlet-class找到DispatcherServlet,根据init-param来获取spring的…...
【开源】基于Vue.js的音乐偏好度推荐系统的设计和实现
项目编号: S 012 ,文末获取源码。 \color{red}{项目编号:S012,文末获取源码。} 项目编号:S012,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、系统设计2.1 功能模块设计2.1.1 音乐档案模块2.1…...
采集1688整店商品(店铺所有商品、店铺列表api)
返回数据: 请求链接 {"user": [],"items": {"item": [{"num_iid": "738354436678","title": "国产正品i13 promax全网通5G安卓智能手机源头厂家批发手机","pic_url": "http…...
IObit Unlocker丨解除占用程序软件
更多内容请收藏:https://rwx.tza-3.xyz 官网:IObit Unlocker “永远不用担心电脑上无法删除的文件。” 界面简单,支持简体中文,一看就会,只需要把无法删除/移动的文件或整个U盘拖到框里就行。 解锁率很高,…...
开发一款小程序游戏需要多少钱?
小程序游戏的开发成本因多种因素而异,无法提供具体的固定数字。以下是影响小程序游戏开发成本的一些关键因素: 游戏规模和复杂度: 小程序游戏可以是简单的休闲游戏,也可以是更复杂的策略游戏。规模和复杂度会影响开发所需的时间和…...
基于Vue+SpringBoot的校园电商物流云平台开源项目
项目编号: S 034 ,文末获取源码。 \color{red}{项目编号:S034,文末获取源码。} 项目编号:S034,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 商品数据模块2.3 快…...
庖丁解牛:NIO核心概念与机制详解 03 _ 缓冲区分配、包装和分片
文章目录 Pre概述缓冲区分配和包装 (allocate 、 wrap)缓冲区分片 (slice)缓冲区份片和数据共享只读缓冲区 (asReadOnlyBuffer)直接和间接缓冲区 (allocateDirect)内存映射文件 I/O将文件映射到内存(map) Pre 庖丁解牛࿱…...
002 OpenCV dft 傅里叶变换
目录 一、傅里叶变换 1.1 傅里叶变换概念 1.2 opencv中傅里叶变换 二、实验代码 一、环境 本文使用环境为: Windows10Python 3.9.17opencv-python 4.8.0.74 二、傅里叶变换 2.1 傅里叶变换概念 傅里叶变换(Fourier Transform)是一种…...
力扣:171. Excel 表列序号(Python3)
题目: 给你一个字符串 columnTitle ,表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 来源:力扣(LeetCode) …...
C++中结构体的初始化
C中结构体的初始化 结构体是一个由程序员定义的数据类型,可以容纳许多不同的数据值。在过去,面向对象编程的应用尚未普及之前,程序员通常使用这些从逻辑上连接在一起的数据组合到一个单元中。一旦结构体类型被声明并且其数据成员被标识&…...
vue3+vite+ts 发布自定义组件到npm
vue3vite 发布自定义组件到npm 初始化项目编写组件配置打包组件上传到npm测试组件库 初始化项目 // 创建项目 pnpm create vite vue-test-app --template vue-ts// 运行项目 cd vite vue-test-app pnpm install pnpm run dev编写组件 1、根目录下创建packages目录作为组件的开…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
