LeetCode--HOT100题(22)
目录
- 题目描述:160. 相交链表(简单)
- 题目接口
- 解题思路
- 代码
- PS:
题目描述:160. 相交链表(简单)
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal- 相交的起始节点的值。如果不存在相交节点,这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中(从头节点开始)跳到交叉节点的节点数skipB- 在listB中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点headA和headB传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
LeetCode做题链接:LeetCode-相交链表
示例 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 中第四个节点) 在内存中指向相同的位置。
注意:示例1中,虽然看上去listA = [4,1,8,4,5], listB = [5,6,1,8,4,5],是从1开始相交,但是它们在内存中指向两个不同的位置
示例 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
如果 listA 和 listB 没有交点,intersectVal 为 0
如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]
进阶: 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?
题目接口
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {}
}
解题思路
参考题解:图解相交链表

- pA走过的路径为A链+B链
- pB走过的路径为B链+A链
- pA和pB走过的长度都相同,都是A链和B链的长度之和,相当于将两条链从尾端对齐,如果相交,则会提前在相交点相遇;如果没有相交点,则会在最后相遇,也就是一起为null。
代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) { // 要么pA和pB一起为null,没有交集;要么就到第一个相交的节点pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}
成功!

PS:
感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个赞喔~
相关文章:
LeetCode--HOT100题(22)
目录 题目描述:160. 相交链表(简单)题目接口解题思路代码 PS: 题目描述:160. 相交链表(简单) 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表…...
产品体系架构202308版
1.前言 当我们不断向前奔跑时,需要回头压实走过的路。不断扩张的同时把相应的内容沉淀下来,为后续的发展铺垫基石。 不知从何时起,产品的架构就面向了微服务/中台化/前后端分离/低代码化/分布式/智能化/运行可观测化的综合体,让…...
Linux systemctl 简单介绍与使用
在Linux下,systemctl是一个管理系统服务的命令。它提供了对systemd服务的控制和管理。 在系统中使用systemctl命令,您可以执行以下操作: 启动服务:systemctl start servicename停止服务:systemctl stop servicename重…...
恺英网络宣布:与华为鸿蒙系统展开合作,将开发多款手游
8月5日消息,恺英网络宣布旗下子公司盛和网络参加了华为开发者大会(HDC.Together)游戏服务论坛,并在华为鸿蒙生态游戏先锋合作启动仪式上进行了亮相。恺英网络表示,将逐步在HarmonyOS上开发多款游戏,利用Har…...
Vue CORS
使用Vue框架报错,客户端浏览器有CORS错误,怎么解决? 参考API Proxying During Development,可以新增或修改config/index.js下的proxyTable属性。 留意到 proxyTable的key值为/api,代表所有服务端域名都改成以/api开头…...
Godot 4 源码分析 - 文件读入编码处理
今天需要读入xml文件进行处理,结果读入一个带中文的文件时,出错了。当然程序还能运行,但编译器一直报错,而且XML解析也不正确 单步调试发现读入的内容出现乱码,具体逻辑: String FileAccess::get_as_text…...
Linux 中使用 verdaccio 搭建私有npm 服务器
安装 Node Linux中安装Node 安装verdaccio npm i -g verdaccio安装完成 输入verdaccio,出现下面信息代表安装成功,同时输入verdaccio后verdaccio已经处于运行状态,当然这种启动时暂时的,我们需要通过pm2让verdaccio服务常驻 ygiZ2zec61wsg…...
C++入门之stl六大组件--stack和queue源码深度剖析及模拟实现
目录 前言 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的模拟实现 三、priority_queue的介绍和使用 1.priority_queue的介绍 2.priority_queue的使用 3.priority_queue的模…...
MyCat配置文件schema.xml讲解
1.MyCat配置 1.1 schema标签 如果checkSQLschema配置的为false,那么执行DB01.TB_ORDER时就会报错,必须用use切换逻辑库以后才能进行查询。 sqlMaxLimit如果未指定limit进行查询,列表查询模式默认为100,最多只查询100条。因为用mycat后默认数…...
Grafana集成prometheus(2.Grafana安装)
查找镜像 docker search grafana下载指定版本 docker pull grafana/grafana:10.0.1启动容器脚本 docker run -d -p 3000:3000 --namegrafana grafana/grafana:10.0.1查看是否启动 docker ps防火墙开启 检查防火墙3000端口是否开启 默认用户及密码 admin/admin 登录 ht…...
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列
代码随想录算法训练营第五十七天| 647. 回文子串 516.最长回文子序列 一、力扣647. 回文子串 题目链接 思路:对于字符串cabac,其中a,b,c,aba,cabac,都是回文子串,如果当前的字串是回文字串,那么它的字串中也会有回文…...
django 优化方式
前言 对于网站和Web APP来说,相同的类型的产品,响应速度越好,那么用户量就越高。不可否认的是,响应速度是用户黏粘性最好的方式之一,但往往不知道如何下手解决,希望这篇文章可以给予你一些思路 对于网站和…...
IDEA中怎么使用git下载项目到本地,通过URL克隆项目(giteegithub)
点击 新建>来自版本控制的项目 点击后会弹出这样一个窗口 通过URL拉取项目代码 打开你要下载的项目仓库 克隆>复制 gitee github也是一样的 返回IDEA 将刚刚复制的URL粘贴进去选择合适的位置点击克隆 下载完成...
09. Docker Compose
目录 1、前言 2、安装Docker Compose 2.1、Docker Compose版本 2.2、下载安装 3、初试Docker Compose 3.1、传统方案部署应用 3.2、使用编排部署应用 3.3、其他命令 3.3.1、ps 3.3.2、images 3.3.3、depends_on 3.3.4、scale 4、小结 1、前言 随着应用架构的不段…...
如何在shell脚本将node_modules里的文件复制一份到public文件里
项目背景:由于公司网络不连接公网,所以在绘制地图大屏项目时,需要我们将边界线数据包也部署起来,来获取边界线数据 解决方案: 1.让后端写个接口或者找个地方将数据包放到服务器即可 2.将数据包放到vue项目的public文…...
监控Redis的关键指标
Redis 也是一个对外服务,所以 Google 的四个黄金指标同样适用于 Redis。 1、延迟 在软件工程架构中,之所以选择 Redis 作为技术堆栈的一员,大概率是想要得到更快的响应速度和更高的吞吐量,所以延迟数据对使用 Redis 的应用程序至…...
Openlayers和leaflet如何选用?
在地图处理这块,Openlayers和Leaflet是非常有名的两个开源的JS框架,他们各有各的优势和劣势,对于刚刚步入此行业的开发者而言怎么选择框架呢? 作者做过一定的探索,在这里将成果分享给大家。 Openlayers 简介 Openlayers是一个基于Javacript开发,免费、开源的前端地图开…...
跟我学C++中级篇——三五法则
一、三五法则 三五法则,这个叫着有点上头,说实话,这个三五法则,未来会不会变成三六或者四七法则,没人知道,反正现在是三五法则。在《cPrimer》第四版中,叫三法则,在第五版第13.1.4章…...
aardio:用 WebView 模仿 mdict 界面
aardio:用 WebView 模仿 mdict 界面 import win.ui; /*DSG{{*/ mainForm win.form(text"aardio2";right889;bottom467) mainForm.add( button{cls"button";text"go";left335;top22;right399;bottom41;z2}; button2{cls"button…...
linq中的操作符
LINQ(Language Integrated Query)是一种用于.NET平台的查询语言,用于查询和操作各种数据源,如集合、数据库和XML。LINQ提供了一组标准查询操作符,用于执行各种查询操作。 LINQ(Language Integrated Query&…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
Python爬虫实战:研究Restkit库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...
