相交链表(LeetCode 160)
文章目录
- 1.问题描述
- 2.难度等级
- 3.热门指数
- 4.解题思路
- 方法一:暴力法
- 方法二:哈希表
- 方法三:双栈
- 方法四:双指针:记录链表长度
- 方法五:双指针:互换遍历
- 5.实现示例
- 参考文献
1.问题描述
给两个单链表的头节点 headA 和 headB ,请找出并返回两个单链表相交的起始节点。如果不存在相交节点,返回 null 。
题目数据保证整个链式结构中不存在环。
注意,函数返回结果后,链表必须保持其原始结构。
示例 1:
相交返回结点 8。
示例 2:
相交返回结点 2。
示例 3:
不相交返回 null。
进阶: 你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?
2.难度等级
Easy。
3.热门指数
★★★★★
出题公司:阿里、腾讯、字节。
4.解题思路
解这道题之前,我们需要首先明确一个概念:何为相交?
相交指的是结点为同一个结点,那么指向结点的指针是相同的,而不是第一个结点值相同。
如果不考虑时间和空间复杂度,那么有多种解法。
假设 m 和 n 是分别是链表 headA 和 headB 的长度。
方法一:暴力法
从头开始遍历第一个链表,遍历第一个链表的每个节点时,同时从头到尾遍历第二个链表,看是否有相同的节点,第一次找到相同的节点即第一个交点。
若第一个链表遍历结束后,还未找到相同的节点,即不存在交点。
时间复杂度: O ( n 2 ) O(n^2) O(n2)。
空间复杂度: O ( 1 ) O(1) O(1)。
方法二:哈希表
判断两个链表是否相交,可以使用哈希集合存储链表节点。
首先遍历链表 headA,将链表中的每个节点加入哈希表中。然后遍历链表 headB,判断节点是否在哈希表中。
如果链表 headB 中的所有节点都不在哈希集合中,则两个链表不相交,返回 null。
时间复杂度: O(m+n),需要遍历两个链表各一次。
空间复杂度: O(m),需要使用哈希表存储链表 headA 的全部节点。
方法三:双栈
我们可以从头遍历两个链表。创建两个栈,第一个栈存储第一个链表的节点,第二个栈存储第二个链表的节点。每遍历到一个节点时,就将该节点入栈。两个链表都入栈结束后。
则通过判断栈顶的节点是否相等即可判断两个单链表是否相交。因为我们知道,若两个链表相交,则从第一个相交节点开始,后面的节点都相交。
若两链表相交,则循环出栈,直到遇到两个出栈的节点不相同,则这个节点的后一个节点就是第一个相交的节点。
时间复杂度: O(m+n)。需要遍历两个链表各两次,一次是入栈,一次是出栈。
空间复杂度: O(m+n),需要使用两个栈存储链表 headA 和 headB 的所有结点。
方法四:双指针:记录链表长度
同时遍历两个链表到尾部,同时记录两个链表的长度。若两个链表最后的一个节点相同,则两个链表相交。
有两个链表的长度后,我们就可以知道哪个链表长,设较长的链表长度为 len1,短的链表长度为 len2。
则先让较长的链表向后移动 len1-len2 个长度。然后开始从当前位置同时遍历两个链表,当遍历到的链表的节点相同时,则这个节点就是第一个相交的节点。
时间复杂度: O ( m + n ) O(m+n) O(m+n),两个指针同时遍历两个链表,然后再遍历两个链表至相同结点。
空间复杂度: O ( 1 ) O(1) O(1)。
方法五:双指针:互换遍历
当链表 headA 和 headB 都不为空时,创建两个指针 pA 和 pB,初始时分别指向两个链表的头节点 headA 和 headB,然后将两个指针依次遍历两个链表的每个节点。具体做法如下:
-
每步操作需要同时更新指针 pA 和 pB。
-
如果指针 pA 不为空,则将指针 pA 移到下一个节点;如果指针 pB 不为空,则将指针 pB 移到下一个节点。
-
如果指针 pA 为空,则将指针 pA 移到链表 headB 的头节点;如果指针 pB 为空,则将指针 pB 移到链表 headA 的头节点。
-
当指针 pA 和 pB 指向同一个节点或者都为空时,返回它们指向的节点或者 null。
为什么第一次遍历完后互换从头遍历后,如果相交会同时到达相交结点呢?
假设下面是一个相交的两个链表,省去了结点。其中链表 headA 的长度为 a + c = m,链表 headB 的长度为 b + c = n。
因为 a + c + b 等于 b + c + a,所以第一次遍历完后互换从头遍历,会同时到达相交结点。
如果两个链表不相交,也会同时到达尾结点,因为 m + n 等于 n + m。
时间复杂度: O ( m + n ) O(m+n) O(m+n),两个指针同时遍历两个链表,然后再遍历两个链表至相同结点。
空间复杂度: O ( 1 ) O(1) O(1)。
5.实现示例
面以 Golang 为例,给出「双指针:互换遍历」的实现。
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {pA, pB := headA, headBfor pA != nil || pB != nil {if pA == pB {return pA}if pA == nil {pA = headB} else {pA = pA.Next}if pB == nil {pB = headA} else {pB = pB.Next} }return nil
}
参考文献
160. 相交链表 - LeetCode
判断两个单链表是否相交及找到第一个交点原创 -CSDN
相关文章:

相交链表(LeetCode 160)
文章目录 1.问题描述2.难度等级3.热门指数4.解题思路方法一:暴力法方法二:哈希表方法三:双栈方法四:双指针:记录链表长度方法五:双指针:互换遍历 5.实现示例参考文献 1.问题描述 给两个单链表的…...

C++多态(详解)
一、多态的概念 1.1、多态的概念 多态:多种形态,具体点就是去完成某个行为,当不同的对象去完成时会产生出不同的状态。 举个例子:比如买票这个行为,当普通人买票时,是全价买票;学生买票时&am…...

06、基于内容的过滤算法Tensorflow实现
06、基于内容的过滤算法Tensorflow实现 开始学习机器学习啦,已经把吴恩达的课全部刷完了,现在开始熟悉一下复现代码。全部工程可从最上方链接下载。 05、基于梯度下降的协同过滤算法中已经介绍了协同过滤算法的基本实现方法,但是这种方法仅…...

html/css中用float实现的盒子案例
运行效果: 代码部分: <!doctype html> <html> <head> <meta charset"utf-8"> <title>无标题文档</title> <style type"text/css">.father{width:300px; height:400px; background:gray;…...

simulink中 Data store memory、write和read模块及案例介绍
目录 1.Data store memory模块 2.data store write模块 3.data store read模块 4.仿真分析 4.1简单使用三个模块 4.2 模块间的调用顺序剖析 1.Data store memory模块 向右拖拉得到Data store read模块,向左拉得到Data write模块 理解:可视为定义变量…...

java设计模式学习之【装饰器模式】
文章目录 引言装饰器模式简介定义与用途实现方式 使用场景优势与劣势装饰器模式在Spring中的应用画图示例代码地址 引言 在日常生活中,我们常常对基本事物添加额外的装饰以增强其功能或美观。例如,给手机加一个保护壳来提升其防护能力,或者在…...

Ubuntu宝塔面板本地部署Emlog个人博客网站并远程访问【内网穿透】
文章目录 前言1. 网站搭建1.1 Emolog网页下载和安装1.2 网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2.Cpolar稳定隧道(云端设置)2.3.Cpolar稳定隧道(本地设置) 3. 公网访问测试总结 前言 博客作为使…...
简述IO流的使用以及使用时需要注意的事项
Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍介绍IO流的使用以及使用时需要注意的事项以及部分理论知识 🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁 🍉博主收将持续更新学习记录获,友友们有任何问题可…...

西工大计算机学院计算机系统基础实验一(函数编写11~14)
稳住心态不要慌,如果考试周冲突的话,可以直接复制这篇博客和上一篇博客西工大计算机学院计算机系统基础实验一(函数编写1~10)-CSDN博客最后的代码,然后直接提交,等熬过考试周之后回过头再慢慢做也可以。 第…...

Spring 声明式事务
Spring 声明式事务 1.Spring 事务管理概述1.1 事务管理的重要性1.2 Spring事务管理的两种方式1.2.1 编程式事务管理1.2.2 声明式事务管理 1.3 为什么选择声明式事务管理 2. 声明式事务管理2.1 基本用法2.2 常用属性2.2.1 propagation(传播行为)2.2.2 iso…...

通达OA inc/package/down.php接口存在未授权访问漏洞
声明 本文仅用于技术交流,请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,文章作者不为此承担任何责任。 一. 产品简介 通达OA(Office Anywhere网络智能办公系统&am…...

数据库原理: 笛卡儿积
笛卡儿积(Cartesian Product)是集合论中的一个概念,也在数据库中的查询操作中经常使用。笛卡儿积是指两个集合(或更多集合)之间所有可能的组合。如果有两个集合A和B,它们的笛卡儿积记作A B,表示…...

docker安装配置prometheus+node_export+grafana
简介 Prometheus是一套开源的监控预警时间序列数据库的组合,Prometheus本身不具备收集监控数据功能,通过获取不同的export收集的数据,存储到时序数据库中。Grafana是一个跨平台的开源的分析和可视化工具,将采集过来的数据实现可视…...

【JavaScript】JS——Map数据类型
【JavaScript】JS——Map数据类型 什么是Map?特性Map与Object的比较 map的创建map的属性map相关方法map的遍历 什么是Map? 存储键值对的对象。 能够记住键的原始插入顺序任何值(对象或原始值)都可以作为键或值。 特性 Map中的一个键只能出现一次&am…...

【【FPGA的 MicroBlaze 的 介绍与使用 】】
FPGA的 MicroBlaze 的 介绍与使用 可编程片上系统(SOPC)的设计 在进行系统设计时,倘若系统非常复杂,采用传统 FPGA 单独用 Verilog/VHDL 语言进行开发的方式,工作量无疑是巨大的,这时调用 MicroBlaze 软核…...
PyQt pdf格式保存
参考文章 pyqt5:利用QFileDialog从本地选择图片\文本文档显示到label、保存图片\label文本到本地(附代码)_pyqt5中qfiledialog.getopenfileurl-CSDN博客 txt文件的打开与保存 def openTextFile(self): # 选择文本文件上传fd,fp QFileDialog.getOpen…...

微前端介绍
目录 微前端概念 微前端特性 场景演示 微前端方案 iframe 方案 qiankun 方案 micro-app 方案 EMP 方案 无界微前端 方案 无界方案 成本低 速度快 原生隔离 功能强大 总结 前言:微前端已经是一个非常成熟的领域了,但开发者不管采用哪个现…...
工业机器视觉megauging(向光有光)使用说明书(一,轻量级的visionpro)
机器视觉megauging(未名之光,向光有光)程序软件资源已经发布,欢迎下载尝新 8:11 2023/12/2 首先,既然觉得可以发表了,就发表。 其次,我这个人没写过什么软件使用说明书,既然走到这路…...
Java——面试:String 和 StringBuffer 的区别?
相同点: String 和 StringBuffer,它们可以储存和操作字符串, 即包含多个字符的字符数据。 String 和 StringBuffer 的区别有以下几点: 1.String 类提供了数值不可改变的字符串。而 StringBuffer 类提供的字符串进行修改。 当你知…...

图扑软件受邀出席高交会-全球清洁能源创新博览会
“相聚鹏城深圳,共享能源盛宴” 第二十五届中国国际高新技术成果交易会(简称“高交会”)于 11 月 15-18 日在深圳盛大开幕。高交会由商务部、科学技术部、工业和信息化部、国家发展改革委、农业农村部、国家知识产权局、中国科学院、中国工程院和深圳市人民政府共同…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
面试高频问题
文章目录 🚀 消息队列核心技术揭秘:从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"?性能背后的秘密1.1 顺序写入与零拷贝:性能的双引擎1.2 分区并行:数据的"八车道高速公路"1.3 页缓存与批量处理…...