160. 相交链表、Leetcode的Python实现

 博客主页:🏆看看是李XX还是李歘歘 🏆

🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺

💗点关注不迷路,总有一些📖知识点📖是你想要的💗

⛽️今天的内容是   Leetcode 160. 相交链表   ⛽️💻💻💻

160. 相交链表

给你两个单链表的头节点 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 个节点。

示例 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) 内存的解决方案?使用双指针a和b,a先遍历headA再遍历headB,b先遍历headB再遍历headA,这样的话,a和b所遍历的长度都是m+n,当a,b分别在第二次经过相交节点的时候,肯定会会相遇。

# 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) -> Optional[ListNode]:if headA is None or headB is None :return NonetmpA,tmpB = headA,headBwhile tmpA!=tmpB :if tmpA is None:tmpA=headBelse :tmpA=tmpA.nextif tmpB is None:tmpB=headAelse :tmpB=tmpB.nextreturn tmpB

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/177934.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity Perception合成数据生成、标注与ML模型训练

在线工具推荐&#xff1a; Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 3D场景编辑器 任何训练过机器学习模型的人都会告诉你&#xff0c;模型是从数据得到的&#xff0c;一般来说&#xff0c;更多的数据和标签会带来更好的性能。 …

垃圾分类箱通过工业4G路由器实现无人值守远程管理

据今年发布的相关数据统计&#xff0c;人们日常生活中每人每天至少能制造1.2kg垃圾&#xff0c;在环保事业中日常垃圾处理已经成为一项紧迫且不可忽视的任务。为了实现城市清洁和环境保护&#xff0c;越来越多的地区开始引入垃圾分类箱。传统的垃圾分类箱管理方式存在着一些不便…

【APP】go-musicfox - 一款网易云音乐命令行客户端, 文件很小Mac版本只有16.5M

go-musicfox 是用 Go 写的又一款网易云音乐命令行客户端&#xff0c;支持各种音质级别、UnblockNeteaseMusic、Last.fm、MPRIS 和 macOS 交互响应&#xff08;睡眠暂停、蓝牙耳机连接断开响应和菜单栏控制等&#xff09;等功能特性。 预览 启动 启动界面 主界面 主界面 通…

网络工程师-入门基础课:华为HCIA认证课程介绍

【微/信/公/众/号&#xff1a;厦门微思网络】 华为HCIA试听课程&#xff1a;超级实用&#xff0c;华为VRP系统文件详解 华为HCIA试听课程&#xff1a;不会传输层协议&#xff0c;HCIA都考不过 华为HCIA试听课程&#xff1a;网络工程师的基本功&#xff1a;网络地址转换NAT 一…

16. 机器学习 - 决策树

Hi&#xff0c;你好。我是茶桁。 在上一节课讲SVM之后&#xff0c;再给大家将一个新的分类模型「决策树」。我们直接开始正题。 决策树 我们从一个例子开始&#xff0c;来看下面这张图&#xff1a; 假设我们的x1 ~ x4是特征&#xff0c;y是最终的决定&#xff0c;打比方说是…

linux下mysql-8.2.0集群部署(python版本要在2.7以上)

目录 一、三台主机准备工作 1、mysql官方下载地址&#xff1a;https://dev.mysql.com/downloads/ 2、修改/etc/hosts 3、关闭防火墙 二、三台主机安装mysql-8.2.0 1、解压 2、下载相应配置 3、初始化mysql&#xff0c;启动myslq&#xff0c;设置开机自启 4、查看初始密…

华为云资源搭建过程

网络搭建 EIP&#xff1a; 弹性EIP&#xff0c;支持IPv4和IPv6。 弹性公网IP&#xff08;Elastic IP&#xff09;提供独立的公网IP资源&#xff0c;包括公网IP地址与公网出口带宽服务。可以与弹性云服务器、裸金属服务器、虚拟IP、弹性负载均衡、NAT网关等资源灵活地绑定及解绑…

学习python必会知识点:if条件判断语句的运用

大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 如果有什么疑惑/资料需要的可以点击文章末尾名片领取源码 if的基本格式 if语句用来做判断&#xff0c;并选择要执行的语句分支。 基本格式如下&#xff1a; if CONDITION1:code_block(1) elif CONDITION2:code_block(2) elif CO…

Spring Task(定时任务)框架

文章目录 一、Spring Task介绍二、cron表达式1.cron表达式介绍2.cron表达式在线生成器 三、fixedDelay四、fixedRate五、initialDelay六、Spring Task的使用1.导入maven坐标spring-context2.启动类添加注解EnableScheduling开启任务调度3.自定义定时任务类 一、Spring Task介绍…

机器人仿真-gazebo学习笔记(4)xacro和传感器添加

1.xacro简介 URDF文件不具备代码复用的特性&#xff08;在上一篇文章也能发现&#xff0c;其实左右轮是极其相似的但还是要单独描述&#xff09;&#xff0c;一个复杂的机器人模型会拥有大量了的传感器和关节组件&#xff0c;这时候使用URDF文件就太难阅读了。精简化、可复用、…

汇编-算术运算符

下面给出了一些有效表达式和它们的值&#xff1a;

【uniapp+vue3】scroll-view实现纵向自动滚动及swiper实现纵向自动滚动

scroll-view本身不支持自动滚动&#xff0c;通过scroll-top属性控制滚动&#xff0c;但是不可以循环滚动 <scroll-view class"notice-bar" scroll-y"true" ref"scrollViewRef" :scroll-top"data.scrollViewTop"scroll-with-animati…

内涝积水监测的效果怎么样?城市内涝怎么监测?

近些年来全球气候变暖带来极端天气的频繁出现&#xff0c;尤其在一些季节之中&#xff0c;暴雨现象的出现会导致城市严重的内涝现象&#xff0c;路面积水问题不仅影响道路交通安全&#xff0c;而且也给市民生命安全带来威胁&#xff0c;背后存在的安全隐患&#xff0c;更是城市…

nmap 使用方法详细介绍

nmap的使用 前言nmap 作用Nmap使用教程 nmap的基本输入&#xff1a;扫描参数&#xff1a;端口扫描&#xff1a;端口状态扫描&#xff1a;UDP扫描协议扫描 总结 Nmap的基础知识Nmap的扫描技术 Nmap的OS检测&#xff08;O&#xff09;Nmap的操作系统指纹识别技术&#xff1a; 前…

网络套接字编程(三)

网络套接字编程(三) 文章目录 网络套接字编程(三)简易日志组件引入日志的原因日志等级打印日志函数将日志组件使用到服务端中 守护进程概念进程组、终端、会话守护进程的实现原理守护进程化组件将守护进程化组件使用到服务端中 补充知识关于inet_ntoa 在上一篇博客 网络套接字…

【Apache Flink】Flink DataStream API的基本使用

Flink DataStream API的基本使用 文章目录 前言1. 基本使用方法2. 核心示例代码3. 完成工程代码pom.xmlWordCountExample测试验证 4. Stream 执行环境5. 参考文档 前言 Flink DataStream API主要用于处理无界和有界数据流 。 无界数据流是一个持续生成数据的数据源&#xff0…

git命令清单

一、设置和配置 1.初始化一个新的仓库&#xff1a; git init2.克隆&#xff08;Clone&#xff09;一个远程仓库到本地&#xff1a; git clone <repository_url>3.配置用户信息&#xff1a; git config --global user.name "Your Name" git config --global…

疑难杂症-暂时不能解析域名“mirrors.tuna.tsinghua.edu.cn”

可能是太久没用Ubuntu了&#xff0c;总是有一些莫名其妙的问题 我的方法简单粗暴&#xff1a;不需要重启&#xff0c;打开终端&#xff0c;输入sudo apt-get update&#xff0c;解析成功 还有一些别的方法&#xff0c;不过我也没试过 修改/etc/resolv.conf还是修改/etc/resol…

客户端与服务端实时通讯(轮询、websocket、SSE)

客户端与服务端实时通讯 背景 在某些项目中&#xff0c;某些数据需要展示最新的&#xff0c;实时的&#xff0c;这时候就需要和服务端进行长时间通讯 方案 对于数据实时获取&#xff0c;我们一般会有4种方案&#xff1a; 1.短轮询&#xff1a;使用浏览器的定时器发起http请…

两个字符串的删除操作

题目描述 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。 示例 思路 其实这道题的思路和最长公共子序列的思路一致&#xff0c;本题让我们求word1 和 word2 相同所需的最小步数&#xff0…