【刷题笔记9.25】LeetCode:相交链表

LeetCode:相交链表

一、题目描述

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、分析及代码

方法一:使用哈希Set集合

(注意:集合中存储的是ListNode节点的地址,并非数值***,换句话说即使链表A和链表B都有值为1的节点,但实质上其还是两个不同的节点,因为内存地址是不一样的,只有都指向同一个相交的节点了其内存地址才是相同的)

判断两个链表是否相交,可以使用哈希集合存储链表节点。

首先遍历链表 headA,并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB,对于遍历到的每个节点,判断该节点是否在哈希集合中:

  • 如果当前节点不在哈希集合中,则继续遍历下一个节点;
  • 如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表 headB中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点,返回该节点。
  • 如果链表 headB 中的所有节点都不在哈希集合中,则两个链表不相交,返回 null。

上代码:

public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}//声明集合SetSet<ListNode> set = new HashSet<>();ListNode temp = headA;while (temp != null) {set.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (set.contains(temp)) {return temp;}temp = temp.next;}return null;}

方法二:两层while循环遍历

(注意:使用此方法注意while循环的判断条件是对headA 和 headB判断而不是headA.next 和 headB.next,因为会有这种情况:链表A和链表B都只要一个节点且为同一个节点的情况

在这里插入图片描述


上代码:

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode p = headA;while (p != null) {ListNode q = headB;while (q != null) {if (p == q) {return p;}q = q.next;}p = p.next;}return null;}

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

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

相关文章

【面试算法——动态规划 19】最长回文子序列 (hard)让字符串成为回文串的最少插入次数

516. 最长回文子序列 链接: 516. 最长回文子序列 给你一个字符串 s &#xff0c;找出其中最长的回文子序列&#xff0c;并返回该序列的长度。 子序列定义为&#xff1a;不改变剩余字符顺序的情况下&#xff0c;删除某些字符或者不删除任何字符形成的一个序列。 示例 1&…

opencv for unity package在unity中打开相机不需要dll

下载OpenCV for Unity 导入后&#xff0c;里面有很多案例 直接打开就可以运行 打开相机

TCP 和 UDP哪个更好

传输控制协议 &#xff08;TCP&#xff09; 和用户数据报协议 &#xff08;UDP&#xff09; 是互联网的基础支柱&#xff0c;支持从网络源到目的地的不同类型的数据传输。TCP更可靠&#xff0c;而UDP优先考虑速度和效率。本文解释了两种协议的工作原理&#xff0c;并详细讨论了…

vuejs - - - - - 使用code编辑器codemirror

使用code编辑器codemirror 0. 效果图1. 依赖安装2. 组件封装3. 组件使用 0. 效果图 列表实现参考: 列表实现代码 1. 依赖安装 npm install codemirror codemirror-editor-vue3 jsonlint-mod 2. 组件封装 code-mirror-editor.vue <template><VueCodeMirrorclas…

Java之IO流概述

1.1 什么是IO 生活中&#xff0c;你肯定经历过这样的场景。当你编辑一个文本文件&#xff0c;忘记了ctrls &#xff0c;可能文件就白白编辑了。当你电脑上插入一个U盘&#xff0c;可以把一个视频&#xff0c;拷贝到你的电脑硬盘里。那么数据都是在哪些设备上的呢&#xff1f;键…

Nginx WEB访问与Linux授权约束

看到所有文件的权限都是没有的&#xff0c;即便所有的权限都没有即使nginx做了配置&#xff0c;这些都是正确的。那么在浏览器真正去访问的时候是不能访问的。 [rootjenkins html]# ls -l total 4 drwxr-xr-x 2 root root 23 Sep 16 17:43 dist ---------- 1 root root 33 Sep …

利用C++开发一个迷你的英文单词录入和测试小程序-增强功能

小玩具基本完成之后&#xff0c;在日常工作中&#xff0c;记录一些单词&#xff0c;然后定时再复习下&#xff0c;还真的有那么一点点用&#xff08;毕竟自己做的小玩具&#xff09;。 在使用过程中&#xff0c;遇到不认识的单词&#xff0c;总去翻译软件翻译&#xff0c;然后…

蓝桥杯每日一题2023.9.24

九进制转十进制 - 蓝桥云课 (lanqiao.cn) 题目描述 分析 #include<bits/stdc.h> using namespace std; int main() {cout << 2 * 9 * 9 * 9 0 * 9 * 9 2 * 9 2;return 0; } 顺子日期 - 蓝桥云课 (lanqiao.cn) 题目描述 分析 全部枚举 #include<bits/s…

MAC word 如何并列排列两张图片

系统&#xff1a;MAC os 参考博客 https://baijiahao.baidu.com/s?id1700824516945958911&wfrspider&forpc 步骤1 新建一个word文档和表格 修改表格属性 去掉自动重调尺寸以适应内容 插入图片 在表格的位置插入对应的图片如下 去除边框 最终结果如下

腾讯mini项目-【指标监控服务重构】2023-08-27

今日已办 Docker Monitoring with cAdvisor, Prometheus and Grafana Docker Monitoring with cAdvisor, Prometheus and Grafana | by Mertcan Simsek | MediumMonitoring Docker container metrics using cAdvisor | Prometheus prometheus.yml global:scrape_interval: …

macOS 下 Termius 中文显示为乱码

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是 DevO…

94 # express 兼容老的路由写法

上一节实现了错误处理中间件&#xff0c;这一节来实现兼容老的路由写法 看个 express 的二级路由的例子 const express require("express"); const userRouter require("./routes/userRouter"); const articleRouter require("./routes/articleR…

Python爬虫技术系列-02HTML解析-xpath与lxml

Python爬虫技术系列-02HTML解析-xpath与lxml 2 XPath介绍与lxml库2.1 XPath概述2.2 lxml库介绍2.2.1 lxml库安装2.2.2 lxml库基本使用2.2.3 lxml案例a.读取数据并补全b.读取数据并选取节点&#xff1a; 2 XPath介绍与lxml库 参考连接&#xff1a; XPath教程 https://www.w3sch…

高效管理生活:Microsoft To Do for Mac 微软待办事项软件

在日常生活中&#xff0c;我们经常面临着琐碎的任务和繁忙的安排。为了更好地管理自己的时间和事务&#xff0c;一款强大而智能的待办事项软件是必不可少的。Microsoft To Do for Mac 微软待办事项软件将助您高效管理生活&#xff0c;让每件事都尽在掌握。 Microsoft To Do fo…

腾讯mini项目-【指标监控服务重构-会议记录】2023-07-26

2023-07-26组长会议纪要 A组 项目对齐和问题 分配需求&#xff0c;SLI指标上报&#xff0c;暂时没有实际效果 每个人负责一条指标&#xff0c;同步代码&#xff0c;时间问题还是难题跟B组同学请教&#xff0c;答疑 问题&#xff1a;启动 Tracer 【已解决】 环境问题&#xf…

数据结构:堆的简单介绍

目录 堆的介绍:(PriorityQueue) 大根堆:根节点比左右孩子节点大 小根堆:根节点比左右孩子节点小 堆的存储结构: 为什么二叉树在逻辑上用满二叉树结构,而不是普通二叉树呢? 因为如果是普通二叉树会造成资源的浪费​编辑 堆的介绍:(PriorityQueue) 堆又称优先级队列,何为优先…

uni-app使用HBuilder X编辑器本地打包apk步骤说明

1.下载安装Android Studio 下载地址官方地址&#xff1a;Android Studio 下载文件归档 | Android 开发者 | Android Developers 安装Android SDK和Google USB Driver即可&#xff0c;后者主要是为了后期使用USB设置的&#xff0c;如果不需要可以不点。 2.下载uni-app提供…

ElementUI之登陆+注册->饿了吗完成用户登录界面搭建,axios之get请求,axios之post请求,跨域,注册界面

饿了吗完成用户注册登录界面搭建axios之get请求axios之post请求跨域注册界面 1.饿了吗完成用户注册登录界面搭建 将端口号8080改为8081 导入依赖&#xff0c;在项目根目录使用命令npm install element-ui -S&#xff0c;添加Element-UI模块 -g&#xff1a;将依赖下载node_glod…

大数据flink篇之一-基础知识

一、起源 2010至2014年间&#xff0c;由柏林工业大学、柏林洪堡大学和哈索普拉特纳研究所联合发起名Stratosphere的研究项目。2014年4月&#xff0c;项目贡献给Apache基金会&#xff0c;成为孵化项目。更名为Flink2014年12月&#xff0c;成为基金会顶级项目2015年9月&#xff…

02 MIT线性代数-矩阵消元 Elimination with matrices

一, 消元法 Method of Elimination 消元法是计算机软件求解线形方程组所用的最常见的方法。任何情况下&#xff0c;只要是矩阵A可逆&#xff0c;均可以通过消元法求得Axb的解 eg: 我们将矩阵左上角的1称之为“主元一”&#xff08;the first pivot&#xff09;&#xff0c;第…