当前位置: 首页 > news >正文

160. 相交链表

题目描述

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

图示两个链表在节点 c1 开始相交**:**

在这里插入图片描述

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headAheadB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案

示例 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 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listAlistB 没有交点,intersectVal0
  • 如果 listAlistB 有交点,intersectVal == listA[skipA] == listB[skipB]

**进阶:**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?

解答

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// pA 和 pB先走A链表和B链表,然后再切换另一个链表走,有交点就能找到// 没交点最后两指针都同时到nullptrListNode *pA = headA, *pB = headB;while(pA != pB){pA = (pA == NULL ? headB : pA->next);pB = (pB == NULL ? headA : pB->next);}return pA;}
};

相关文章:

160. 相交链表

题目描述 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交**&#xff1a;** 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函…...

【MFC】12.双缓冲序列化机制-笔记

双缓冲 双缓冲在之前写字符雨的时候&#xff0c;已经简单介绍过&#xff0c;今天我们来写一个简单的程序来体会双缓冲机制 我们实现一个在屏幕上画直线的功能&#xff1a; 在类中添加变量&#xff0c;保存起点坐标和终点坐标&#xff1a; //定义一个容器&#xff0c;保存每…...

Linux 终端会话中,启动任务并放到后台运行

一、需求 linux要执行一个脚本&#xff0c;耗时很长&#xff0c;想要脚本在后台运行&#xff0c;用户注销或终端软件关闭时也可以继续运行。 二、实现 1、nohup命令 脚本在后台运行 nohup 是在 Linux 和类 Unix 系统中使用的一个命令&#xff0c;用于在后台运行程序&#x…...

软考笔记——10.项目管理

进度管理 进度管理就是采用科学的方法&#xff0c;确定进度目标&#xff0c;编制进度计划和资源供应计划&#xff0c;进行进度控制&#xff0c;在与质量、成本目标协调的基础上&#xff0c;实现工期目标。 具体来说&#xff0c;包括以下过程&#xff1a; (1) 活动定义&#…...

算法与数据结构(二十四)最优子结构原理和 dp 数组遍历方向

注&#xff1a;此文只在个人总结 labuladong 动态规划框架&#xff0c;仅限于学习交流&#xff0c;版权归原作者所有&#xff1b; 本文是两年前发的 动态规划答疑篇open in new window 的修订版&#xff0c;根据我的不断学习总结以及读者的评论反馈&#xff0c;我给扩展了更多…...

Java Vue Uniapp MES生产执行管理系统

本MES系统是一款B/S结构、通用的生产执行管理系统&#xff0c;功能强大&#xff01; 系统基于多年离散智造行业的业务经验组建&#xff0c;主要目的是为国内离散制造业的中小企业提供一个专业化、通用性、低成本的MES系统解决方案。 联系作者获取...

深入探究Socks5代理与IP代理在网络安全与爬虫中的应用

1. Socks5代理&#xff1a;打开网络隧道的多功能工具 Socks5代理是一种流行的代理协议&#xff0c;它在传输层为数据包提供了隧道。相较于之前的版本&#xff0c;Socks5不仅支持TCP连接&#xff0c;还可以处理UDP流量&#xff0c;使其在需要实时数据传输的应用中表现出色。在网…...

Vue使用jspdf和html2canvas组件库结合导出PDF文件

效果图&#xff1a; 1、安装依赖&#xff1a; npm install html2canvas --save npm install jspdf --save 或 yarn add html2canvas --save yarn add jspdf --save 2、封装全局调用方法&#xff1a;this.$exportPDF(#id,文件名) 新建js文件&#xff1a;/utils/html2Pdf.js&am…...

7. 实现 API 自动生成

目录 1. pom.xml中引用依赖 2. 引入相关的依赖 3. 编写配置类 4. application.yml 中添加配置 5. API 常用注解 6. 访问 API 列表 7. API 导入 Postman 使用 Springfox Swagger生成 API&#xff0c;并导入 Postman&#xff0c;完成API单元测试。 Swagger 简介&#xff1a;Swag…...

使用Druid解析SQL,获取SQL中所有使用的表

一、sqlParse组成 Druid SQL Parser分三个模块&#xff1a; - Parser - AST - Visitor 1.1 Parser parser是将输入文本转换为ast&#xff08;抽象语法树&#xff09;&#xff0c;parser有包括两个部分&#xff0c;Parser和Lexer&#xff0c;其中Lexer实现词法分析&#x…...

公司内部测试团队可以替代专业的软件检测机构吗,性能测试怎么收费?

第三方软件测试 尽管软件测试是伴随着软件开发的发展而产生的&#xff0c;但是在信息技术日新月异的今天&#xff0c;软件测试逐渐走出开发附庸的定位。 一方面&#xff0c;很多大型企业都在内部设置了专门的测试团队以承接软件系统的测试工作&#xff0c;为产品质量把关。另…...

Three.js之相机、渲染器、光源、动画、性能监测

参考资料 第一个3D案例—透视投影相机第一个3D案例—渲染器…Canvas画布布局和全屏 知识点 透视投影相机PerspectiveCameraWebGL渲染器WebGLRenderer辅助观察坐标系AxesHelper漫反射网格材质MeshLambertMaterial点光源PointLight点光源辅助观察PointLightHelper环境光Ambien…...

Seaborn图表使用指南!

目录 介绍线图散点图直方图概率密度函数 &#xff08;PDF&#xff09;箱线图小提琴剧情配对图热图关节图地毯图 一、介绍 数据科学已成为一个突出的领域&#xff0c;近年来呈爆炸性增长。对精通从数据中获取见解并应用这些见解来解决现实世界问题的数据科学家的需求从未增加。…...

[C++ 网络协议编程] TCP/IP协议

目录 1. TCP/IP协议栈 2. TCP原理 2.1 TCP套接字中的I/O缓冲 2.2 TCP工作原理 2.2.1 三次握手&#xff08;连接&#xff09; 2.2.2 与对方主机的数据交换 2.2.3 四次握手&#xff08;断开与套接字的连接&#xff09; TCP&#xff08;Transmission Control Protocol传输控…...

Unity用NPOI创建Exect表,保存数据,和修改删除数据。以及打包后的坑——无法打开新创建的Exect表

先说坑花了一下午才找到解决方法解决&#xff0c; 在Unity编辑模式下点击物体创建对应的表&#xff0c;获取物体名字与在InputText填写的注释数据。然后保存。创建Exect表可以打开&#xff0c;打包PC后&#xff0c;点击物体创建的表&#xff0c;打不开文件破损 解决方法&#…...

记一次fegin调用的媒体类型问题

1.问题&#xff1a;分页查询&#xff0c;分页参数传递不生效 2.开发环境&#xff1a;fegin接口 开发环境&#xff1a;调用接口 3.修改后&#xff1a;fegin接口不变 调用接口 前端媒体类型&#xff1a; 问题解决&#xff01;&#xff01;&#xff01; 4.原因分析&…...

在Hive/Spark上运行执行TPC-DS基准测试 (ORC和TEXT格式)

目前,在Hive/Spark上运行TPC-DS Benchmark主要是通过早期由Hortonworks维护的一个项目:hive-testbench 来完成的。本文我们以该项目为基础介绍一下具体的操作步骤。不过,该项目仅支持生成ORC和TEXT格式的数据,如果需要Parquet格式,请参考此文《在Hive/Spark上执行TPC-DS基…...

如何仿写简易tomcat 实现思路+代码详细讲解

仿写之前&#xff0c;我们要搞清楚都要用到哪些技术 自定义注解&#xff0c;比如Tomcat使用的是Servlet&#xff0c;我们可以定义一个自己的MyServlet构造请求体和返回体&#xff0c;比如tomcat使用HttpRequest&#xff0c;我们可以自己定义myHttpRequestjava去遍历一个指定目…...

如何提高深度学习性能

可用于 对抗过度拟合并获得更好泛化能力的20 个提示、技巧和技术 如何从深度学习模型中获得更好的性能? 这是我最常被问到的问题之一。 可能会被问为: 如何提高准确率? ……或者可以反过来说: 如果我的神经网络表现不佳该怎么办? 我经常回答说:“我不太清楚,但我有很…...

ECMAScript版本对比:从ES1到ES2021

引言 ECMAScript&#xff08;简称ES&#xff09;是一种用于编写Web前端JavaScript的标准化语言。自1997年发布第一版&#xff08;ES1&#xff09;以来&#xff0c;ECMAScript已经经历了多个版本的更新和演进。每个版本都引入了新的语法和功能&#xff0c;为开发人员提供了更强…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...