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

相交链表(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实现的盒子案例

运行效果&#xff1a; 代码部分&#xff1a; <!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模块&#xff0c;向左拉得到Data write模块 理解&#xff1a;可视为定义变量…...

java设计模式学习之【装饰器模式】

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

Ubuntu宝塔面板本地部署Emlog个人博客网站并远程访问【内网穿透】

文章目录 前言1. 网站搭建1.1 Emolog网页下载和安装1.2 网页测试1.3 cpolar的安装和注册 2. 本地网页发布2.1 Cpolar临时数据隧道2.2.Cpolar稳定隧道&#xff08;云端设置&#xff09;2.3.Cpolar稳定隧道&#xff08;本地设置&#xff09; 3. 公网访问测试总结 前言 博客作为使…...

简述IO流的使用以及使用时需要注意的事项

Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍介绍IO流的使用以及使用时需要注意的事项以及部分理论知识 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主收将持续更新学习记录获&#xff0c;友友们有任何问题可…...

西工大计算机学院计算机系统基础实验一(函数编写11~14)

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

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&#xff08;传播行为&#xff09;2.2.2 iso…...

通达OA inc/package/down.php接口存在未授权访问漏洞

声明 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 一. 产品简介 通达OA&#xff08;Office Anywhere网络智能办公系统&am…...

数据库原理: 笛卡儿积

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

docker安装配置prometheus+node_export+grafana

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

【JavaScript】JS——Map数据类型

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

【【FPGA的 MicroBlaze 的 介绍与使用 】】

FPGA的 MicroBlaze 的 介绍与使用 可编程片上系统&#xff08;SOPC&#xff09;的设计 在进行系统设计时&#xff0c;倘若系统非常复杂&#xff0c;采用传统 FPGA 单独用 Verilog/VHDL 语言进行开发的方式&#xff0c;工作量无疑是巨大的&#xff0c;这时调用 MicroBlaze 软核…...

PyQt pdf格式保存

参考文章 pyqt5:利用QFileDialog从本地选择图片\文本文档显示到label、保存图片\label文本到本地&#xff08;附代码&#xff09;_pyqt5中qfiledialog.getopenfileurl-CSDN博客 txt文件的打开与保存 def openTextFile(self): # 选择文本文件上传fd,fp QFileDialog.getOpen…...

微前端介绍

目录 微前端概念 微前端特性 场景演示 微前端方案 iframe 方案 qiankun 方案 micro-app 方案 EMP 方案 无界微前端 方案 无界方案 成本低 速度快 原生隔离 功能强大 总结 前言&#xff1a;微前端已经是一个非常成熟的领域了&#xff0c;但开发者不管采用哪个现…...

工业机器视觉megauging(向光有光)使用说明书(一,轻量级的visionpro)

机器视觉megauging&#xff08;未名之光&#xff0c;向光有光&#xff09;程序软件资源已经发布&#xff0c;欢迎下载尝新 8:11 2023/12/2 首先&#xff0c;既然觉得可以发表了&#xff0c;就发表。 其次&#xff0c;我这个人没写过什么软件使用说明书&#xff0c;既然走到这路…...

Java——面试:String 和 StringBuffer 的区别?

相同点&#xff1a; String 和 StringBuffer&#xff0c;它们可以储存和操作字符串&#xff0c; 即包含多个字符的字符数据。 String 和 StringBuffer 的区别有以下几点&#xff1a; 1.String 类提供了数值不可改变的字符串。而 StringBuffer 类提供的字符串进行修改。 当你知…...

图扑软件受邀出席高交会-全球清洁能源创新博览会

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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

【Java】Ajax 技术详解

文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...

多模态学习路线(2)——DL基础系列

目录 前言 一、归一化 1. Layer Normalization (LN) 2. Batch Normalization (BN) 3. Instance Normalization (IN) 4. Group Normalization (GN) 5. Root Mean Square Normalization&#xff08;RMSNorm&#xff09; 二、激活函数 1. Sigmoid激活函数&#xff08;二分类&…...