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

LeetCode--HOT100题(22)

目录

  • 题目描述:160. 相交链表(简单)
    • 题目接口
    • 解题思路
    • 代码
  • PS:

题目描述:160. 相交链表(简单)

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
图示两个链表在节点 c1 开始相交:
在这里插入图片描述
题目数据 保证 整个链式结构中不存在环。

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

自定义评测:

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

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数
    评测系统将根据这些输入创建链式数据结构,并将两个头节点 headAheadB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案

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)

目录 题目描述&#xff1a;160. 相交链表&#xff08;简单&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;160. 相交链表&#xff08;简单&#xff09; 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表…...

产品体系架构202308版

1.前言 当我们不断向前奔跑时&#xff0c;需要回头压实走过的路。不断扩张的同时把相应的内容沉淀下来&#xff0c;为后续的发展铺垫基石。 不知从何时起&#xff0c;产品的架构就面向了微服务/中台化/前后端分离/低代码化/分布式/智能化/运行可观测化的综合体&#xff0c;让…...

Linux systemctl 简单介绍与使用

在Linux下&#xff0c;systemctl是一个管理系统服务的命令。它提供了对systemd服务的控制和管理。 在系统中使用systemctl命令&#xff0c;您可以执行以下操作&#xff1a; 启动服务&#xff1a;systemctl start servicename停止服务&#xff1a;systemctl stop servicename重…...

恺英网络宣布:与华为鸿蒙系统展开合作,将开发多款手游

8月5日消息&#xff0c;恺英网络宣布旗下子公司盛和网络参加了华为开发者大会&#xff08;HDC.Together&#xff09;游戏服务论坛&#xff0c;并在华为鸿蒙生态游戏先锋合作启动仪式上进行了亮相。恺英网络表示&#xff0c;将逐步在HarmonyOS上开发多款游戏&#xff0c;利用Har…...

Vue CORS

使用Vue框架报错&#xff0c;客户端浏览器有CORS错误&#xff0c;怎么解决&#xff1f; 参考API Proxying During Development&#xff0c;可以新增或修改config/index.js下的proxyTable属性。 留意到 proxyTable的key值为/api&#xff0c;代表所有服务端域名都改成以/api开头…...

Godot 4 源码分析 - 文件读入编码处理

今天需要读入xml文件进行处理&#xff0c;结果读入一个带中文的文件时&#xff0c;出错了。当然程序还能运行&#xff0c;但编译器一直报错&#xff0c;而且XML解析也不正确 单步调试发现读入的内容出现乱码&#xff0c;具体逻辑&#xff1a; String FileAccess::get_as_text…...

Linux 中使用 verdaccio 搭建私有npm 服务器

安装 Node Linux中安装Node 安装verdaccio npm i -g verdaccio安装完成 输入verdaccio,出现下面信息代表安装成功&#xff0c;同时输入verdaccio后verdaccio已经处于运行状态&#xff0c;当然这种启动时暂时的&#xff0c;我们需要通过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&#xff0c;那么执行DB01.TB_ORDER时就会报错&#xff0c;必须用use切换逻辑库以后才能进行查询。 sqlMaxLimit如果未指定limit进行查询&#xff0c;列表查询模式默认为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. 回文子串 题目链接 思路&#xff1a;对于字符串cabac&#xff0c;其中a,b,c,aba,cabac&#xff0c;都是回文子串&#xff0c;如果当前的字串是回文字串&#xff0c;那么它的字串中也会有回文…...

django 优化方式

前言 对于网站和Web APP来说&#xff0c;相同的类型的产品&#xff0c;响应速度越好&#xff0c;那么用户量就越高。不可否认的是&#xff0c;响应速度是用户黏粘性最好的方式之一&#xff0c;但往往不知道如何下手解决&#xff0c;希望这篇文章可以给予你一些思路 对于网站和…...

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文件里

项目背景&#xff1a;由于公司网络不连接公网&#xff0c;所以在绘制地图大屏项目时&#xff0c;需要我们将边界线数据包也部署起来&#xff0c;来获取边界线数据 解决方案&#xff1a; 1.让后端写个接口或者找个地方将数据包放到服务器即可 2.将数据包放到vue项目的public文…...

监控Redis的关键指标

Redis 也是一个对外服务&#xff0c;所以 Google 的四个黄金指标同样适用于 Redis。 1、延迟 在软件工程架构中&#xff0c;之所以选择 Redis 作为技术堆栈的一员&#xff0c;大概率是想要得到更快的响应速度和更高的吞吐量&#xff0c;所以延迟数据对使用 Redis 的应用程序至…...

Openlayers和leaflet如何选用?

在地图处理这块,Openlayers和Leaflet是非常有名的两个开源的JS框架,他们各有各的优势和劣势,对于刚刚步入此行业的开发者而言怎么选择框架呢? 作者做过一定的探索,在这里将成果分享给大家。 Openlayers 简介 Openlayers是一个基于Javacript开发,免费、开源的前端地图开…...

跟我学C++中级篇——三五法则

一、三五法则 三五法则&#xff0c;这个叫着有点上头&#xff0c;说实话&#xff0c;这个三五法则&#xff0c;未来会不会变成三六或者四七法则&#xff0c;没人知道&#xff0c;反正现在是三五法则。在《cPrimer》第四版中&#xff0c;叫三法则&#xff0c;在第五版第13.1.4章…...

aardio:用 WebView 模仿 mdict 界面

aardio&#xff1a;用 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&#xff08;Language Integrated Query&#xff09;是一种用于.NET平台的查询语言&#xff0c;用于查询和操作各种数据源&#xff0c;如集合、数据库和XML。LINQ提供了一组标准查询操作符&#xff0c;用于执行各种查询操作。 LINQ&#xff08;Language Integrated Query&…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

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样…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...