当前位置: 首页 > 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增删…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...