剑指 Offer II 023. 两个链表的第一个重合节点
comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20023.%20%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E9%87%8D%E5%90%88%E8%8A%82%E7%82%B9/README.md
剑指 Offer II 023. 两个链表的第一个重合节点
题目描述
给定两个单链表的头节点 headA 和 headB ,请找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:

题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Intersected at '8' 解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出:Intersected at '2' 解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [0,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中节点数目为n0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点,intersectVal为0 - 如果
listA和listB有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶:能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?
注意:本题与主站 160 题相同:https://leetcode.cn/problems/intersection-of-two-linked-lists/
解法
方法一:双指针
我们使用两个指针 a a a, b b b 分别指向两个链表 h e a d A headA headA, h e a d B headB headB。
同时遍历链表,当 a a a 到达链表 h e a d A headA headA 的末尾时,重新定位到链表 h e a d B headB headB 的头节点;当 b b b 到达链表 h e a d B headB headB 的末尾时,重新定位到链表 h e a d A headA headA 的头节点。
若两指针相遇,所指向的结点就是第一个公共节点【路径点数一样】。若没相遇,说明两链表无公共节点,此时两个指针都指向 null,返回其中一个即可。
时间复杂度 O ( m + n ) O(m+n) O(m+n),其中 m m m 和 n n n 分别是链表 h e a d A headA headA 和 h e a d B headB headB 的长度。空间复杂度 O ( 1 ) O(1) O(1)。

Python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:a,b=headA,headBwhile a!=b: #退出时:a=b=none or nodea=a.next if a else headBb=b.next if b else headAreturn a
Java
/*** 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) {ListNode a = headA, b = headB;while (a != b) {a = a == null ? headB : a.next;b = b == null ? headA : b.next;}return a;}
}
C++
/*** 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) {ListNode *a = headA, *b = headB;while (a != b) {a = a ? a->next : headB;b = b ? b->next : headA;}return a;}
};
Go
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {a, b := headA, headBfor a != b {if a == nil {a = headB} else {a = a.Next}if b == nil {b = headA} else {b = b.Next}}return a
}
TypeScript
/*** Definition for singly-linked list.* class ListNode {* val: number* next: ListNode | null* constructor(val?: number, next?: ListNode | null) {* this.val = (val===undefined ? 0 : val)* this.next = (next===undefined ? null : next)* }* }*/function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {let a = headA;let b = headB;while (a != b) {a = a ? a.next : headB;b = b ? b.next : headA;}return a;
}
JavaScript
/*** Definition for singly-linked list.* function ListNode(val) {* this.val = val;* this.next = null;* }*//*** @param {ListNode} headA* @param {ListNode} headB* @return {ListNode}*/
var getIntersectionNode = function (headA, headB) {let a = headA;let b = headB;while (a != b) {a = a ? a.next : headB;b = b ? b.next : headA;}return a;
};
Swift
/*** Definition for singly-linked list.* public class ListNode {* public var val: Int* public var next: ListNode?* public init(_ val: Int) {* self.val = val* self.next = nil* }* }*/class Solution {func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {var a = headAvar b = headBwhile a !== b {a = a == nil ? headB : a?.nextb = b == nil ? headA : b?.next}return a}
}
相关文章:
剑指 Offer II 023. 两个链表的第一个重合节点
comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20023.%20%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E7%9A%84%E7%AC%AC%E4%B8%80%E4%B8%AA%E9%87%8D%E5%90%88%E8%8A%82%E7%82%B9/README.md 剑指 Offer II 023. 两…...
个人搭建CDN加速服务 特网科技
在互联网快速发展的今天,网站的加载速度对用户体验有着至关重要的影响,传统的网页加载方式依赖于服务器的性能和网络环境,这使得某些网站的页面加载时间过长,用户体验不佳,为了解决这个问题,许多企业开始采…...
用deepseek学大模型08-卷积神经网络(CNN)
yuanbao.tencent.com 从入门到精通卷积神经网络(CNN),着重介绍的目标函数,损失函数,梯度下降 标量和矩阵形式的数学推导,pytorch真实能跑的代码案例以及模型,数据,预测结果的可视化展示, 模型应用场景和优缺点…...
蓝桥杯单片机基础部分——6、555定时器
前言 NE555是一个纯硬件的设计,旦硬件电路确定了,其功能也确定了,没有可编程的部分,也没什么好去理解的地方,如果理解不了就直接背代码,这里也不是很常考,大家了解一下就可以了,知道…...
Python学习心得函数
一、函数的定义及调用 1.函数的定义: 函数的定义:函数是将一段能实现某种特定功能的代码,使用函数名进行封装,并通过函数名称进行调用。从而达到一次编写,多次调用的目的。 2.函数类型分为两类: &#…...
神经网络实验——MLP
目录 1 目的 2 方法 3 源代码 4 结果 1 目的 ①熟悉 Python 的输入输出流; ②学会使用 matplotlib进行图像可视化; ③掌握神经网络的基本原理,学会使用 sklearn 库中的 MLPClassifier 函数构建基础的多层感知机神经网络分类器; ④学会使用网格查找进行超参数优…...
配置Api自动生成
我的飞书:https://rvg7rs2jk1g.feishu.cn/docx/TVlJdMgYLoDJrsxAwMgcCE14nxt 使用Springfox Swagger生成API,并导入Postman,完成API单元测试 Swagger: 是一套API定义的规范,按照这套规范的要求去定义接口及接口相关信息,再通过可…...
dify-AI 私有部署可修改前端页面
dify文档 官方文档:欢迎使用 Dify | Dify 源码:https://github.com/langgenius/dify.git 安装docker 官网:https://www.docker.com/ 部署服务到docker cd dify cd docker cp .env.example .env docker compose up -d查看效果 http://localh…...
使用 @Results 注解来手动指定字段映射
在 MyBatis 中,Results 注解用于手动指定查询结果的字段映射,尤其当数据库列名与 Java 对象的字段名不一致时。你可以通过 Results 和 Result 注解来精确控制每一列与类属性之间的映射关系。 示例:使用 Results 注解来手动指定字段映射 假设你…...
数据治理中 大数据处理一般都遵循哪些原则
在数据治理中,大数据处理通常遵循以下原则: 最小化原则:企业应只收集实现特定目的所需的数据,避免数据冗余和安全风险。 合法性原则:企业必须遵守相关法律法规,确保数据处理符合法律要求,降低法…...
从0到1:STM32温控系统开发踩坑指南
1. 设计目标 核心功能:实现0-100℃范围内的温度闭环控制 性能指标: 测量精度:0.5℃(使用DS18B20传感器) 控制响应时间:<5秒 显示分辨率:0.1℃ 扩展功能: LCD实时显示当前温度…...
修改时无条件,可以自定义id条件(通过查询)
在这段代码中,$(row).attr(data-rarity, data.rarity); 的作用是给表格的每一行 (row) 添加一个 data-rarity 的自定义属性,属性的值是该行数据中的 rarity 字段。 解释: 1.row 是当前行的 DOM 元素。 2.data.rarity 是从 data 对象中获取的…...
工业制造能耗管理新突破,漫途MTIC-ECM平台助力企业绿色转型!
在工业制造领域,能源消耗一直是企业运营成本的重要组成部分。随着“双碳”目标的推进,如何实现高效能耗管理,成为制造企业亟待解决的问题。漫途MTIC-ECM能源能耗在线监测平台,结合其自研的硬件产品,为工业制造企业提供…...
实现一个简单的协同过滤推荐算法
题目描述: 协同过滤是推荐系统中的一种常用技术,其基本思想是利用用户之间的相似性或物品之间的相似性来进行推荐。本次面试题要求实现一个基于用户的协同过滤推荐算法。 具体要求: 定义两个类:User 和 Item,分别表示用…...
eNSP防火墙综合实验
一、实验拓扑 二、ip和安全区域配置 1、防火墙ip和安全区域配置 新建两个安全区域 ip配置 Client1 Client2 电信DNS 百度web-1 联通DNS 百度web-2 R2 R1 三、DNS透明代理相关配置 1、导入运营商地址库 2、新建链路接口 3、配置真实DNS服务器 4、创建虚拟DNS服务器 5、配置D…...
操作系统知识(二)
1、线程切换进行了哪些动作 在操作系统中,线程切换(也称为上下文切换)是指操作系统将 CPU 的控制权从一个线程转移到另一个线程的过程。这个过程涉及多个步骤和动作,主要包括以下几个方面: 1. 保存当前线程的上下文 …...
图论:tarjan 算法求解强连通分量
题目描述 有一个 n n n 个点, m m m 条边的有向图,请求出这个图点数大于 1 1 1 的强连通分量个数。 输入格式 第一行为两个整数 n n n 和 m m m。 第二行至 m 1 m1 m1 行,每一行有两个整数 a a a 和 b b b,表示有一条…...
Spring中Bean的四种实例化方法
Bean的四种实例化方法 Bean是Spring核心的概念,另外一个核心的概念是AOP。官网上,Bean的解释是: In Spring, the objects that form the backbone of your application and that are managed by the Spring IoC container are called beans…...
专利申请要求
专利申请并不要求发明已经实际制造出来,但需要具备完整且可行的技术方案。以下是详细的解释和申请流程: 一、专利申请的核心要求 技术方案而非实物 专利保护的是创新性的技术方案或设计理念,而非实物产品本身。只要你能清晰描述技术原理、结构…...
解锁 JavaScript 异步编程:Promise 链式操作、async/await 与 Promise.all 深度剖析
1.引言 在 JavaScript 的世界里,异步编程是一个核心且关键的概念。随着 Web 应用的复杂度不断提升,处理多个异步操作的需求也日益增长。传统的回调函数方式容易陷入 “回调地狱”,让代码的可读性和可维护性大打折扣。而 Promise 的出现为异步编程带来了新的曙光,后续又衍生…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
