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

leetcode160:相交链表

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

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

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

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

自定义评测:

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

intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
listA - 第一个链表
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 中节点数目为 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) 内存的解决方案?

Related Topics
哈希表
链表
双指针

方法一:使用HashSet

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<>();while (headA != null) {set.add(headA);headA = headA.next;}while (headB != null) {if (!set.add(headB)) {return headB;}headB = headB.next;}return null;}
}

方法二:使用双指针

使用两个指针分别指向两个链表的头节点,然后同时移动。若两个链表相交,那么只要从长链表中从尾节点到短链表长度的距离开始遍历,就会遍历到相同节点

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode a = headA;ListNode b = headB;while (a != b) {a = a == null ? headB : a.next;b = b == null ? headA : b.next;}return a;}
}

相关文章:

leetcode160:相交链表

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

基于Prometheus的jvm监控指标详解

使用Prometheus 监控Springboot应用参考 Prometheus Operator实战—— Prometheus、Alertmanager、Grafana 监控Springboot服务 下面来看看jvm的监控指标 # HELP jvm_gc_collection_seconds Time spent in a given JVM garbage collector in seconds. # TYPE jvm_gc_collection…...

C程序设计语言基础

机器语言与高级语言 计算机硬件只能够识别电平信号&#xff0c;正电平或负电平&#xff0c;计算机的的各种按钮触发各种电平与计算机交互。随着随着操作系统的发展&#xff0c;人们用1&#xff0c;0分别表示正电平和负电平&#xff0c;并由0&#xff0c;1所组成的一系列指令指…...

构建同一局域网下文件共享网页

首先&#xff0c;我会将这个内容分成以下步骤&#xff1a; 目录 1. 安装必要的软件和工具 2. 搭建本地服务器 3. 编写账号系统和登录页面 4. 实现多人登录 5. 实现文件上传和共享功能 以下是每个步骤的详细说明和代码示例。 1. 安装必要的软件和工具 为了完成这个项目&…...

程序员未来是不是会大量失业?

程序员宝藏库&#xff1a;https://gitee.com/sharetech_lee/CS-Books-Store 会&#xff0c;但是主要原因并不是来自最近爆火的AIGC。 生成式AI对比与传统的工具的确很强大&#xff0c;但是要说替代某种工作岗位还为时尚早。最近铺天盖地的相关推文&#xff0c;热度一波未平又起…...

解密普元大文件传输平台新版本21种特性

本文主要介绍大文件传输平台及其传输特性&#xff0c;以平台版本升级为切入点&#xff0c;探讨大文件传输平台对多种传输场景的支持及部署管控方面能力的增强。目 录01 普元大文件传输平台‍‍02 普元文件传输平台新版本特性‍‍‍‍‍‍03 信创项目案例‍‍04 总结01普元大…...

每日一问-ChapGPT-20230406-中医基础-脉诊

文章目录每日一问-ChapGPT系列起因每日一问-ChapGPT-20230406-中医基础-脉诊脉诊脉诊的左右手脉诊拓展01沉脉:02迟脉:03促脉:04代脉:05动脉:06短脉:07伏脉:08浮脉:09革脉:10洪脉:11滑脉:12缓脉:13疾脉:14结脉:15紧脉:16芤脉:17散脉:18牢脉:19弦脉:20弱脉:21濡脉:22细脉:23微脉:…...

Nuxt项目asyncData服务端请求数据渲染

或许有些人会比较喜欢在mounted里去请求数据 但在Nuxt项目中是绝对不能这样操作的 因为 mounted的特性也说的比较明白了 当页面挂载完之后执行 但显然 seo只读你页面挂载的内容 如果你在这请求 那么对不起 你请求回来的数据渲染到界面上seo爬虫是看不到的 Nuxt项目请求数据 可…...

Vue 13 - 列表渲染 v-for

V-for介绍 当使用Vue.js框架时&#xff0c;可以使用v-for指令对数据进行循环遍历并渲染到模板中。v-for可以遍历数组、对象、字符串、指定次数等。 以下是v-for的用法&#xff1a; 遍历数组 <div v-for"(item, index) in items" :key"index"> {{…...

XML复习

目录什么是XMLXML中的内容可以干什么XML文件的创建以及其格式XML的文档约束-DTD约数XML的文档约束-schema约束Dom4J 解析XML 文档什么是XML XML 全称(extensible Markup Lanage) 可扩展标记语言它是一种数据的表示形式, 可以存储复杂的数据格式以及我们自己定义的格式.XML经常…...

【python设计模式】10、组合模式

哲学思想 组合模式是一种设计模式&#xff0c;用于将对象组合成树形结构以表示部分-整体层次结构。该模式允许客户端统一处理单个对象和对象组合。 从哲学的角度来看&#xff0c;组合模式可以被视为关于整体和部分之间关系的哲学思想。在这个模式中&#xff0c;整体和部分之间…...

实验五 网络安全加固

目录 一、实验内容 二、实验环境 三、实验步骤 一、实验内容 在GRE VPN实验基础上&#xff0c;对网络进行安全加固。 1、在S0上配置端口安全&#xff0c;设置服务器端口MAC绑定、限制端口MAC连接数量为1&#xff0c;超过最大值则丢弃数据帧。 2、配置OSPF路由协议认证。 3…...

MongoDB综述【入门指南】

写这篇博客,正好是2023年4月5日15:29:31,是清明节,放假一天,我坐在我的小小租房室内,思考着没思考到啥,哈哈哈,感觉好着急啊!看完了一本《城南旧事》,但是就是不踏实,好吧~我来写一篇最近在学的一个技术 为了更优秀的自己~奥利给!! 首先,我们从最初级小白开始(因为自己也是小白…...

Python 3 备忘清单_开发速查表分享

Python 3 备忘清单 Python 3开发速查备忘单是 Python 3 编程语言的单页参考表入门&#xff0c;为开发人员分享快速参考备忘单。 开发速查表大纲 入门 介绍 Hello World 变量 数据类型 Slicing String Lists If Else 循环 函数 文件处理 算术 加等于 f-字符串(Python 3.6) P…...

Thinkphp 6.0模版的加载包含输出

本节课我们来学习一下模版标签中的文件的包含、输出以及加载。 一&#xff0e;包含文件 1. 使用{include}标签来加载公用重复的文件&#xff0c;比如头部、尾部和导航部分&#xff1b; 2. 在模版 view 目录创建一个 public 公共目录&#xff0c;分别创建 header、footer 和 nav…...

ROS实践11 自定义头文件并调用

文章目录运行环境&#xff1a;思路&#xff1a;1.1 编写头文件1.2 includepath添加头文件路径1.3 编写可执行文件1.4 配置文件1.5 编译运行运行环境&#xff1a; ubuntu20.04 noetic 宏基暗影骑士笔记本 思路&#xff1a; 类和函数&#xff1a; 头文件 声明 可执行文件 定义…...

一位年薪35W的测试被开除,回怼的一番话,令人沉思

一位年薪35W测试工程师被开除回怼道&#xff1a;“反正我有技术&#xff0c;在哪不一样” 一技傍身&#xff0c;万事不愁&#xff0c;当我们掌握了一技之长后&#xff0c;在职场上说话就硬气了许多&#xff0c;不用担心被炒&#xff0c;反过来还可以炒了老板&#xff0c;这一点…...

【Docker】Docker常用命令

帮助启动类命令 启动docker systemctl start docker停止docker systemctl stop docker重启docker systemctl restart docker查看docker状态 systemctl status docker[root192 ~]# systemctl status docker ● docker.service - Docker Application Container EngineLoaded…...

【linux基础】7.linux系统自定义应用名和应用图标

"懦弱之人毫无价值"1. 做应用和图标1.1.测试和加入侧边栏3. 命令行重命名唤醒任务叙述&#xff1a;有一个x.sh文件可以在命令行执行,sh x.sh&#xff0c;这样太麻烦。 将其做成app且配上logo&#xff0c;下次直接点击使用将其路径全名重命名&#xff0c;可以直接用重…...

10.网络爬虫—MongoDB详讲与实战

网络爬虫—MongoDB详讲与实战MongoDBMongoDB安装创建数据目录1.数据库操作2.集合操作3.文档操作4.索引操作5.聚合操作6.备份与恢复MongoDB增删改查mongodb集合的增删改查数据插入到表数据的查看删除数据更新数据PyMongo连接数据库第二步 选择需要使用的数据库和集合PyMongo增删…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...