网页视频下载手机/重庆seo代理计费
摘要
剑指 Offer 52. 两个链表的第一个公共节点
一、双指针解法
使用双指针的方法,可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时,两个链表才可能相交。因此首先判断链表 headA和 headB是否为空,如果其中至少有一个链表为空,则两个链表一定不相交,返回 null。
当链表 headA和 headB 都不为空时,创建两个指针pA 和pB,初始时分别指向两个链表的头节点 headA和 headB,然后将两个指针依次遍历两个链表的每个节点。具体做法如下:
- 每步操作需要同时更新指针 pA 和 pB。
- 如果指针 pA不为空,则将指针 pA移到下一个节点;如果指针 pB 不为空,则将指针 pB 移到下一个节点。
- 如果指针 pA 为空,则将指针 pA移到链表headB 的头节点;如果指针 pB为空,则将指针 pB 移到链表 headA的头节点。
- 当指针pA 和pB指向同一个节点或者都为空时,返回它们指向的节点或者 null。
package Linklist;import java.util.HashSet;
import java.util.Set;/*** @Classname JZ52两个链表的第一个公共节点* @Description TODO* @Date 2023/2/11 13:39* @Created by xjl*/
public class JZ52两个链表的第一个公共节点 {public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}// 采用的是双指针的方式ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA;ListNode pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}// 使用的是双指针来实现ListNode getIntersectionNodecpoy(ListNode headA, ListNode headB) {if (headA==null|| headB==null){return null;}ListNode pA=headA;ListNode pB=headB;while (pA!=pB){pA=pA==null?headB:pA.next;pB=pB==null?headA:pB.next;}return pA;}}
复杂度分析
- 时间复杂度:O(m+n),其中 m 和 n 是分别是链表headA 和 headB 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。
- 空间复杂度:O(1)。
二、哈希集合解法
判断两个链表是否相交,可以使用哈希集合存储链表节点。
- 首先遍历链表 headA,并将链表 headA中的每个节点加入哈希集合中。然后遍历链表 headB,对于遍历到的每个节点,判断该节点是否在哈希集合中:
- 如果当前节点不在哈希集合中,则继续遍历下一个节点;
- 如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都是两个链表的公共节点,因此在链表 head 中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点,返回该节点。
如果链表 headB中的所有节点都不在哈希集合中,则两个链表不相交,返回 null。
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
复杂度分析
- 时间复杂度是O(m+n), m、n分别是链表headA和headB的长度。需要遍历两个链表的各一次。
- 空间复杂度m,m 是链表 headA的长度。需要使用哈希集合存储链表 headA中的全部节。
博文参考
《Leetcode》
相关文章:

剑指 Offer 52. 两个链表的第一个公共节点
摘要 剑指 Offer 52. 两个链表的第一个公共节点 一、双指针解法 使用双指针的方法,可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时,两个链表才可能相交。因此首先判断链表 headA和 headB是否为空,如果其中至少有一个链表为…...

可以写进简历的软件测试电商项目,不进来get一下?
前言 说实话,在找项目的过程中,我下载过(甚至付费下载过)N多个项目、联系过很多项目的作者,但是绝大部分项目,在我看来,并不适合你拿来练习,它们或多或少都存在着“问题”ÿ…...

蓝桥杯-算法-印章问题
这个题真的顶啊!思路:n种图案,m张印章,每一个图案的概率是1/n,这个概率以后用P表示首先我们定义dp[i][j]是买了i张印章(对应于上面的m),凑齐j种图案的概率(对应于上面的n…...

戴尔游匣G16电脑U盘安装系统操作教程分享
戴尔游匣G16电脑U盘安装系统操作教程分享。有用户在使用戴尔游匣G16电脑的时候遇到了系统问题,比如电脑蓝屏、自动关机重启、驱动不兼容等问题。遇到这些问题如果无法进行彻底解决,我们可以通过U盘重新安装系统的方法来解决,因为这些问题一般…...

2023数学建模美赛赛题思路分析 2023美赛 美国大学生数学建模数模
将在本帖更新2023美国大学生数学建模数模美赛各个赛题思路,大家可以点赞收藏! 一、参赛报名 组队参赛(每队人数3人,专业不限)。 二、赛题思路及资料 会在本帖更新思路分析,Q群可领取模型代码/赛题思路资料…...

vue3与vue2的对比
Vue 3.0 和 Vue 2.0 是 Vue 前端框架的两个主要版本,它们有着不同的更新和优化: Vue 3.0 主要更新内容: 采用 TypeScript 作为开发语言,提高了代码的类型安全性。 速度更快,内存使用更少,支持大规模数据处…...

史上最全软件测试工程师常见的面试题总结(百度、oppo、中软国际、华为)备战金三银四
1、面试:神州数码1.介绍你下你项目中一个自动化实现的流程2.你觉得做自动化的意义在哪里 >需要对之前已经实现的功能进行回归测试、保证当前版本更新的内容不能影响到之前已经实现好的功能3.你们做自动化产生了什么结果 >测试报告、报错截图和报错日志、测试报…...
“深度学习”学习日记。卷积神经网络--用CNN的实现MINIST识别任务
2023.2.11 通过已经实现的卷积层和池化层,搭建CNN去实现MNIST数据集的识别任务; 一,简单CNN的网络构成: 代码需要在有网络的情况下运行,因为会下载MINIST数据集,运行后会生成params.pkl保留训练权重&…...

JavaWeb--JDBC练习
JDBC练习5.1 需求5.2 案例实现5.2.1 环境准备5.2.2 查询所有5.2.3 添加数据5.2.4 修改数据5.2.5 删除数据5.1 需求 完成商品品牌数据的增删改查操作 查询:查询所有数据添加:添加品牌修改:根据id修改删除:根据id删除 5.2 案例实…...

【LeetCode】2335. 装满杯子需要的最短总时长
2335. 装满杯子需要的最短总时长 题目描述 现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount ,其中 amount[0]、amount[1] 和 a…...

Android 12.0 通过驱动实现禁用usb鼠标和usb键盘功能
1.1概述 在12.0的系统产品定制化开发中,在进行定制中有关于usb键盘和usb鼠标的需求中,产品要求禁止usb口挂载usb鼠标和usb键盘,所以需要要求在usb挂载类型的时候 判断如果是usb鼠标和usb键盘就不让挂载,这就需要从驱动方面入手来解决这个问题,接下来看下驱动的某些挂载usb…...

C++入门——内存管理
C入门——内存管理 C/C内存分布 分类是为了更好的管理 int globalVar 1; static int staticGlobalVar 1; void Test() {static int staticVar 1;int localVar 1;int num1[10] {1, 2, 3, 4};char char2[] "abcd";char* pChar3 "abcd";int* ptr1 (…...

MySQL-InnoDB行格式浅析
简介 我们知道读写磁盘的速度非常慢,和内存读写差了几个数量级,所以当我们想从表中获取某些记录时, InnoDB 存储引擎需要一条一条的把记录从磁盘上读出来么? 不,那样会慢死,InnoDB 采取的方式是:…...

AXI 总线协议学习笔记(4)
引言 前面两篇博文从简单介绍的角度说明了 AXI协议规范。 AXI 总线协议学习笔记(2) AXI 总线协议学习笔记(3) 从本篇开始,详细翻译并学习AXI协议的官方发布规范。 文档中的时序图说明: AXI指࿱…...

C++复习笔记6
1.String类的实现 注意深浅拷贝, C语言字符串拼接函数strcat() #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vld.h> #include<assert.h> using namespace std;class String {friend ostream& operator<<(ostream &am…...

指针的步长及意义(C语言基础)
指针的步长及意义 文章目录指针的步长及意义指针变量1后偏移的字节数不同指针解引用时取出的字节数不同其他例子不同类型的指针有何不同的意义指针变量1后跳跃字节数量不同解引用的时候,取出字节数量不同 指针变量1后偏移的字节数不同 代码演示:&#…...

SpringMVC:统一异常处理(11)
统一异常处理1. 说明2. 问题描述3. 异常处理器使用3.1 创建异常处理器类3.2 让程序抛出异常3.3 测试4. 项目异常处理方案4.1 异常分类4.2 异常解决方案4.3 异常解决方案的具体实现4.4 测试5. 总结1. 说明 \quad本篇文章是在文章SpringMVC:SSM整合(Spring…...

SpringBoot的配置与使用
SpringBoot简介 我们的Spring是包含了众多工具的IoC容器,而SpringBoot则是Spring的加强版,可以更加方便快捷的使用 如果Spring是手动挡的车,那么SpringBoot就是自动挡的车,让我们的驾驶体验变得更好 SpringBoot具有一下几种特征…...

【Python】tkinter messagebox练习笔记
我一好友在朋友圈看到人家用代码花式秀恩爱,让我也做一个,我就用我学习半年python的功力,做了这一个东西。🙏窗口主页面(图一)为了让我这个盆友有颜面,特意做了一个问答问他帅不帅,以…...

2022年12月电子学会Python等级考试试卷(五级)答案解析
青少年软件编程(Python)等级考试试卷(五级) 分数:100 题数:38 一、单选题(共25题,共50分) 1. 下面哪个语句正确定义了元组类型数据tuple1?( ) A. t…...

计算机网络自定向下 -- 浅谈可靠性之rdt协议
可靠性数据传输原理 可靠指数据在传输过程中不错,不丢,不乱 运输层要为应用层提供一种服务:数据可以通过一条可靠的信道进行传输,在该信道中传输的数据不会受到损坏或者丢失, 实现这种服务的是可靠数据传输协议。 要实现这种服…...

制造业升级转型:制造业上市公司-智能制造词频统计数据集
发展智能制造,关乎中国制造业转型升级的成效。基于中国制造业上市公司年报,通过文本数据挖掘,提取关键词反映企业对智能制造的关切焦点,进而运用词频及共词网络分析,洞察中国智能制造的发展态势。 研究发现࿰…...

HTML 开发工具整理
一、千乐微云团队推荐的HTML开发工具Visual Studio Code 简称VS Code (第一推荐)Visual Studio Code (简称 VS Code / VSC) 是一款免费开源的现代化轻量级代码编辑器,支持几乎所有主流的开发语言的语法高亮、智能代码补全、自定义快捷键、括号…...

介绍ACE C++网络通信框架
很久以前笔者也不太熟悉ACE C网络通信框架,偶然的机会逐渐接触后,发现它的优良! 总结来看它的有点如下 非常适合后台无界面网络通信的系统编程 适合小型化核心网使用;但值得注意,如果您需要的是web领域技术栈&…...

【Mac OS】JDK 多版本切换配置
前言 由于不同的项目可能需要使用的 JDK 版本不一样,所以在系统中配置多个 JDK 版本,并且能随时切换,是一个必要的配置。 查看已安装的 JDK 版本 /usr/libexec/java_home -V框框1是执行的命令 框框2是当前系统下所有的 JDK 版本 框框3是当…...

RabbitMQ-Exchanges交换机
一、介绍 RabbitMQ消息传递模型的核心思想是:生产者生产的消息从不会直接发送到队列。实际上,通常生产者甚至不知道这些消息传递到了哪些队列中。相反,生产者只能将消息发送到交换机,交换机工作的内容非常简单,一方…...

离散数学 课时二 命题逻辑等值演算
等值式(等值联结词) 1、设A、B是两个命题公式,若A、B构成的等价式 A等价于B 为重言式,那么称A与B是等值的 2、常用等值式: 注意: 1 双否定律 2 幂等律 3 交换律 4 结合律 5 吸收律 6 德摩根律 7 同一律 8 零律 9 矛盾律 10 排中律 11 蕴含表达式 12 …...

Debezium系列之:事件扁平化转换SMT,简化debezium数据格式,为数据添加head,为值添加键值对
Debezium系列之:事件扁平化转换SMT,简化debezium数据格式,为数据添加head,为值添加键值对 一、需求背景二、Debezium数据格式和扁平化数据格式对比三、事件扁平化SMT作用四、事件扁平化转换SMT设置五、事件扁平化参数详解六、完整SMT参数配置一、需求背景 Debezium 数据更改…...

内网渗透(十八)之Windows协议认证和密码抓取-本地认证(NTML哈希和LM哈希)
系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...

Portraiture全新4.0最新版人像磨皮插件更新内容
Portraiture是一款智能磨皮插件,为Photoshop和Lightroom添加一键磨皮美化功能,快速对照片中皮肤、头发、眉毛等部位进行美化,无需手动调整,大大提高P图效率。全新4版本,升级AI算法,并独家支持多人及全身模式…...