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

LeetCode 160.相交链表

在这里插入图片描述

文章目录

  • 💡题目分析
  • 💡解题思路
    • 🚩步骤一:找尾节点
    • 🚩步骤二:判断尾节点是否相等
    • 🚩步骤三:找交点
      • 🍄思路1
      • 🍄思路2
  • 🔔接口源码

在这里插入图片描述
题目链接👉 LeetCode 160.相交链表👈

💡题目分析

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

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

💡解题思路

🚩步骤一:找尾节点

	struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1,lenB = 1;while(tailA){tailA = tailA->next;lenA++;}while(tailB){tailB = tailB->next;lenB++;}

🚩步骤二:判断尾节点是否相等

判断尾节点是否相等,如果尾节点相等就是相交

if (tailA != tailB)
{return NULL;
}

🚩步骤三:找交点

🍄思路1

A链表所有节点跟B链表都比较一遍,相等的那个就是交点

这种暴力求解法解决这道题是没问题的。但是这种解法时间复杂度为 O(N^2) / O(N*M),要求优化到 O(N),所以我们不采用这种暴力解法,建议使用下一种解法👇

🍄思路2

分别定义两个链表的长度 lenA 和 lenB,长的先走abs(lenA - lenB)步(差距步),然后再同时走,第一个相等的就是相交节点

	//长的先走差距步int gap = abs(lenA - lenB); //abs函数是对整数进行取绝对值struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenA < lenB){longList = headB;shortList = headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}

👇图解👇
在这里插入图片描述

此方法整体时间复杂度为:O(M+N) / O(N),空间复杂度为:O(1)

🔔接口源码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* tailA = headA;struct ListNode* tailB = headB;int lenA = 1,lenB = 1;while(tailA){tailA = tailA->next;lenA++;}while(tailB){tailB = tailB->next;lenB++;}//判断最后一个节点是否相等(是否相交)if(tailA != tailB){return NULL;}//长的先走差距步int gap = abs(lenA - lenB);struct ListNode* longList = headA;struct ListNode* shortList = headB;if(lenA < lenB){longList = headB;shortList = headA;}while(gap--){longList = longList->next;}//一一对应比较,判断重叠节点(因为前面已经经过是否相交的判断,所以执行至此,必定是相交的)while(longList != shortList){longList = longList->next;shortList = shortList->next;}//二者相等,任意一一个都是相交起始点return longList;
}

在这里插入图片描述

🥰希望烙铁们能够理解欧!

总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰

请添加图片描述

相关文章:

LeetCode 160.相交链表

文章目录 &#x1f4a1;题目分析&#x1f4a1;解题思路&#x1f6a9;步骤一&#xff1a;找尾节点&#x1f6a9;步骤二&#xff1a;判断尾节点是否相等&#x1f6a9;步骤三&#xff1a;找交点&#x1f344;思路1&#x1f344;思路2 &#x1f514;接口源码 题目链接&#x1f449;…...

【深度学习_TensorFlow】调用keras高层API重写手写数字识别项目

写在前面 上一阶段我们完成了手写数字识别项目的构建&#xff0c;了解了网络构建、训练、测试的基本流程&#xff0c;但是对于一些常见的操作&#xff0c;因其使用过于频繁&#xff0c;实际上并无必要手动实现&#xff0c;而早已被封装为函数了。 这篇文章我们将了解keras高层…...

柔性数组(C语言)

也许你从来没有听说过柔性数组&#xff08; flexible array &#xff09;这个概念&#xff0c;但是它确实是存在的。 C99 中&#xff0c;结构中的最后一个元素允许是未知大小的数组&#xff0c;这就叫做柔性数组成员&#xff0c;但结 构中的柔性数组成员前面必须至少一个其他…...

判断推理 -- 图形推理 -- 属性规律

中心对称&#xff1a;取一个点&#xff0c;穿过中心能找到另一个对称点。把轴对称 中心对称标出来。五角星不是中心对称。 BD对称轴方向相同&#xff0c;但135自带对称轴&#xff0c;24没带&#xff0c;所以6应该不带对称轴。 百分号不是轴对称。 白色对称轴 平行 或者 夹角…...

【注解使用】使用@Autowired后提示:Field injection is not recommended(Spring团队不推荐使用Field注入)

问题发生场景&#xff1a; 在使用 IDEA 开发 SpringBoot 项目时&#xff0c;在 Controller 类中使用注解 Autowired 注入一个依赖出现了警告提示&#xff0c;查看其他使用该注解的地方同样出现了警告提示。这是怎么回事&#xff1f;由于先去使用了SpringBoot并没有对Spring进行…...

Rust语法: 枚举,泛型,trait

这是我学习Rust的笔记&#xff0c;本文适合于有一定高级语言基础的开发者看不适合刚入门编程的人&#xff0c;对于一些概念像枚举&#xff0c;泛型等&#xff0c;不会再做解释&#xff0c;只写在Rust中怎么用。 文章目录 枚举枚举的定义与赋值枚举绑定方法和函数match匹配枚举…...

hivesql-dayofweek 函数

返回日期或时间戳的星期几。 此函数是 extract(DAYOFWEEK FROM expr) 的同义函数。 语法 dayofweek(expr) 参数 expr&#xff1a;一个 DATE 或 TIMESTAMP 表达式。 返回 一个 INTEGER&#xff0c;其中 1 Sunday 和 7 Saturday。 示例 > SELECT dayofweek(2009-07-30)…...

DIP:《Deep Image Prior》经典文献阅读总结与实现

文章目录 Deep Image Prior1. 方法原理1.1 研究动机1.2 方法 2. 实验验证2.1 去噪2.2 超分辨率2.3 图像修复2.4 消融实验 3. 总结 Deep Image Prior 1. 方法原理 1.1 研究动机 动机 深度神经网络在图像复原和生成领域有非常好的表现一般归功于神经网络学习到了图像的先验信息…...

LAXCUS如何通过技术创新管理数千台服务器

随着互联网技术的不断发展&#xff0c;服务器已经成为企业和个人获取信息、进行计算和存储的重要工具。然而&#xff0c;随着服务器数量的不断增加&#xff0c;传统的服务器管理和运维方式已经无法满足现代企业的需求。LAXCUS做为专注服务器集群的【数存算管】一体化平台&#…...

【Java】BF算法(串模式匹配算法)

☀️ 什么是BF算法 BF算法&#xff0c;即暴力算法&#xff0c;是普通的模式匹配算法&#xff0c;BF算法的思想就是将目标串S的第一个与模式串T的第一个字符串进行匹配&#xff0c;若相等&#xff0c;则继续比较S的第二个字符和T的第二个字符&#xff1b;若不相等&#xff0c;则…...

Vue:使用Promise.all()方法并行执行多个请求

在Vue中&#xff0c;可以使用Promise.all()方法来并行执行多个请求。当需要同时执行多个异步请求时&#xff0c;可以将这些请求封装为Promise对象并使用Promise.all()方法来执行它们。 示例1&#xff1a; 以下是一个示例代码&#xff0c;展示了如何通过Promise.all()方法并行…...

21.0 CSS 介绍

1. CSS层叠样式表 1.1 CSS简介 CSS(层叠样式表): 是一种用于描述网页上元素外观和布局的样式标记语言. 它可以与HTML结合使用, 通过为HTML元素添加样式来改变其外观. CSS使用选择器来选择需要应用样式的元素, 并使用属性-值对来定义这些样式.1.2 CSS版本 CSS有多个版本, 每个…...

下一代计算:嵌入AI的云/雾/边缘/量子计算

计算系统在过去几十年中推动了计算机科学的发展&#xff0c;现在已成为企业世界的核心&#xff0c;提供基于云计算、雾计算、边缘计算、无服务器计算和量子计算的服务。现代计算系统解决了现实世界中许多需要低延迟和低响应时间的问题。这有助于全球各地的青年才俊创办初创企业…...

Gitlab-第四天-CD到k8s集群的坑

一、.gitlab-ci.yml #CD到k8s集群的 stages: - deploy-test build-image-deploy-test: stage: deploy-test image: bitnami/kubectl:latest # 使用一个包含 kubectl 工具的镜像 tags: - k8s script: - ls -al - kubectl apply -f deployment.yaml # 根据实际情况替换…...

【Java基础】Java对象的生命周期

【Java基础】Java对象的生命周期 一、概述 一个类通过编译器将一个Java文件编译为Class字节码文件&#xff0c;然后通过JVM中的解释器编译成不同操作系统的机器码。虽然操作系统不同&#xff0c;但是基于解释器的虚拟机是相同的。java类的生命周期就是指一个class文件加载到类…...

【每日一题】88. 合并两个有序数组

【每日一题】88. 合并两个有序数组 88. 合并两个有序数组题目描述解题思路 88. 合并两个有序数组 题目描述 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 …...

Navicat Premium连接sqlserve数据库失败?你需要注意这几点看看配置对了么?

新建数据库连接的时候这么填的信息 报错 原因1&#xff1a;sqlserver数据库的端口和IP地址之间不是&#xff1a;连接而是用&#xff0c;连接 改成如下样式用逗号连接端口和IP地址就好了 原因2&#xff1a;在Navicat Premium中需要安装一个sqlserver的插件 找到安装路径的根目…...

207、仿真-51单片机脉搏心率与血氧报警Proteus仿真设计(程序+Proteus仿真+配套资料等)

毕设帮助、开题指导、技术解答(有偿)见文未 目录 一、硬件设计 二、设计功能 三、Proteus仿真图 四、程序源码 资料包括&#xff1a; 需要完整的资料可以点击下面的名片加下我&#xff0c;找我要资源压缩包的百度网盘下载地址及提取码。 方案选择 单片机的选择 方案一&a…...

flutter 初识(开发体验,优缺点)

前言 最近有个跨平台桌面应用的需求&#xff0c;需要支持 windows/linux/mac 系统&#xff0c;要做个更新应用的小界面&#xff0c;主要功能就是下载更新文件并在本地进行替换&#xff0c;很简单的小功能。 花了几分钟构建没做 UI 优化的示例界面&#xff1a; 由于我们的客…...

校验vue prop的几种方式

校验vue prop的几种方式 vue 要求将传递给组件的任何数据显式声明为 props。此外&#xff0c;它还提供了强大的内置机制来验证该数据。这充当组件和父级组件之间的约定&#xff0c;并确保组件能按预期使用。 让我们看看怎么对props进行校验。它可以帮助我们在开发和调试过程中…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...