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

剑指 Offer 52. 两个链表的第一个公共节点

摘要

剑指 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. 两个链表的第一个公共节点 一、双指针解法 使用双指针的方法&#xff0c;可以将空间复杂度降至 O(1)。只有当链表 headA headB都不为空时&#xff0c;两个链表才可能相交。因此首先判断链表 headA和 headB是否为空&#xff0c;如果其中至少有一个链表为…...

可以写进简历的软件测试电商项目,不进来get一下?

前言 说实话&#xff0c;在找项目的过程中&#xff0c;我下载过&#xff08;甚至付费下载过&#xff09;N多个项目、联系过很多项目的作者&#xff0c;但是绝大部分项目&#xff0c;在我看来&#xff0c;并不适合你拿来练习&#xff0c;它们或多或少都存在着“问题”&#xff…...

蓝桥杯-算法-印章问题

这个题真的顶啊&#xff01;思路&#xff1a;n种图案&#xff0c;m张印章&#xff0c;每一个图案的概率是1/n&#xff0c;这个概率以后用P表示首先我们定义dp[i][j]是买了i张印章&#xff08;对应于上面的m&#xff09;&#xff0c;凑齐j种图案的概率&#xff08;对应于上面的n…...

戴尔游匣G16电脑U盘安装系统操作教程分享

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

2023数学建模美赛赛题思路分析 2023美赛 美国大学生数学建模数模

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

vue3与vue2的对比

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

史上最全软件测试工程师常见的面试题总结(百度、oppo、中软国际、华为)备战金三银四

1、面试&#xff1a;神州数码1.介绍你下你项目中一个自动化实现的流程2.你觉得做自动化的意义在哪里 >需要对之前已经实现的功能进行回归测试、保证当前版本更新的内容不能影响到之前已经实现好的功能3.你们做自动化产生了什么结果 >测试报告、报错截图和报错日志、测试报…...

“深度学习”学习日记。卷积神经网络--用CNN的实现MINIST识别任务

2023.2.11 通过已经实现的卷积层和池化层&#xff0c;搭建CNN去实现MNIST数据集的识别任务&#xff1b; 一&#xff0c;简单CNN的网络构成&#xff1a; 代码需要在有网络的情况下运行&#xff0c;因为会下载MINIST数据集&#xff0c;运行后会生成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 需求 完成商品品牌数据的增删改查操作 查询&#xff1a;查询所有数据添加&#xff1a;添加品牌修改&#xff1a;根据id修改删除&#xff1a;根据id删除 5.2 案例实…...

【LeetCode】2335. 装满杯子需要的最短总时长

2335. 装满杯子需要的最短总时长 题目描述 现有一台饮水机&#xff0c;可以制备冷水、温水和热水。每秒钟&#xff0c;可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。 给你一个下标从 0 开始、长度为 3 的整数数组 amount &#xff0c;其中 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行格式浅析

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

AXI 总线协议学习笔记(4)

引言 前面两篇博文从简单介绍的角度说明了 AXI协议规范。 AXI 总线协议学习笔记&#xff08;2&#xff09; AXI 总线协议学习笔记&#xff08;3&#xff09; 从本篇开始&#xff0c;详细翻译并学习AXI协议的官方发布规范。 文档中的时序图说明&#xff1a; AXI指&#xff1…...

C++复习笔记6

1.String类的实现 注意深浅拷贝&#xff0c; 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后跳跃字节数量不同解引用的时候&#xff0c;取出字节数量不同 指针变量1后偏移的字节数不同 代码演示&#xff1a;&#…...

SpringMVC:统一异常处理(11)

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

SpringBoot的配置与使用

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

【Python】tkinter messagebox练习笔记

我一好友在朋友圈看到人家用代码花式秀恩爱&#xff0c;让我也做一个&#xff0c;我就用我学习半年python的功力&#xff0c;做了这一个东西。&#x1f64f;窗口主页面&#xff08;图一&#xff09;为了让我这个盆友有颜面&#xff0c;特意做了一个问答问他帅不帅&#xff0c;以…...

2022年12月电子学会Python等级考试试卷(五级)答案解析

青少年软件编程&#xff08;Python&#xff09;等级考试试卷&#xff08;五级&#xff09; 分数&#xff1a;100 题数&#xff1a;38 一、单选题(共25题&#xff0c;共50分) 1. 下面哪个语句正确定义了元组类型数据tuple1&#xff1f;&#xff08; &#xff09; A. t…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

0x-3-Oracle 23 ai-sqlcl 25.1 集成安装-配置和优化

是不是受够了安装了oracle database之后sqlplus的简陋&#xff0c;无法删除无法上下翻页的苦恼。 可以安装readline和rlwrap插件的话&#xff0c;配置.bahs_profile后也能解决上下翻页这些&#xff0c;但是很多生产环境无法安装rpm包。 oracle提供了sqlcl免费许可&#xff0c…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

Redis专题-实战篇一-基于Session和Redis实现登录业务

GitHub项目地址&#xff1a;https://github.com/whltaoin/redisLearningProject_hm-dianping 基于Session实现登录业务功能提交版本码&#xff1a;e34399f 基于Redis实现登录业务提交版本码&#xff1a;60bf740 一、导入黑马点评后端项目 项目架构图 1. 前期阶段2. 后续阶段导…...

CCF 开源发展委员会 “开源高校行“ 暨红山开源 + OpenAtom openKylin 高校行活动在西安四所高校成功举办

点击蓝字 关注我们 CCF Opensource Development Committee CCF开源高校行 暨红山开源 openKylin 高校行 西安站 5 月 26 日至 28 日&#xff0c;CCF 开源发展委员会 "开源高校行" 暨红山开源 OpenAtom openKylin 高校行活动在西安四所高校&#xff08;西安交通大学…...