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

Leetcode 02.07 链表相交(链表)

Leetcode 02.07 链表相交(链表)

    • 解法1 尾部对齐
    • 解法2:太厉害了,数学归纳推导的方法

在这里插入图片描述

很巧妙,这就是将链表的尾端对齐后再一起遍历,这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了,数目也一样。

解法1 尾部对齐

时间复杂度O(M+N)
空间复杂度O(1)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int Alen = 0, Blen = 0;if(headA == null || headB == null) return null;// 求两个链表的长度while(curA != null){curA = curA.next;Alen ++;}while(curB != null){curB = curB.next;Blen ++;}curB = headB;curA = headA;// 【长短尾部对齐】让短的那个的头结点还是其之前的头结点,长的的cur右移(长-短)if(Alen > Blen){ for(int i = 0; i < (Alen - Blen); i++){curA = curA.next;}} else if(Alen < Blen){ for(int i = 0; i < (Blen - Alen); i++){curB = curB.next;}}// 接下来curA 和 curB 一起向后移动寻找一样的节点while(curA != null){if(curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}

在这里插入图片描述

解法2:太厉害了,数学归纳推导的方法

在这里插入图片描述

在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a次之后,两个指针会同时到达两个链表相交的节点,该节点也是两个指针第一次同时指向的节点,此时返回相交的节点。
如果两个链表不相交也是一样的道理,当PA指针和PB指针同时遍历m+n后,会同时指向null。在这里插入图片描述

时间复杂度O(1)
空间复杂度O(1)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null) return null;ListNode PA = headA;ListNode PB = headB;// 同时遍历PA,PB,当PA到null则再指向headB,当PB到null则再指向headA// 遇到PA = PB 则返回该值// 最后同时指向null则返回nullwhile(PA != PB){if(PA == null) {PA = headB;continue;}if(PB == null) {PB = headA;continue;}PA = PA.next;PB = PB.next;}if(PA == null) return null;else return PA; }
}    

相关文章:

Leetcode 02.07 链表相交(链表)

Leetcode 02.07 链表相交&#xff08;链表&#xff09; 解法1 尾部对齐解法2&#xff1a;太厉害了&#xff0c;数学归纳推导的方法 很巧妙&#xff0c;这就是将链表的尾端对齐后再一起遍历&#xff0c;这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了&…...

Bootstrap的媒体对象组件(图文展示组件),挺有用的一个组件。

Bootstrap的.media类是用于创建媒体对象的&#xff0c;媒体对象通常用于展示图像&#xff08;图片&#xff09;和文本内容的组合&#xff0c;这种布局在展示新闻文章、博客帖子等方面非常常见。.media类使得创建这样的媒体对象非常简单&#xff0c;通常包含一个图像和相关的文本…...

Day2力扣打卡

打卡记录 无限数组的最短子数组&#xff08;滑动窗口&#xff09; 链接 思路&#xff1a;先求单个数组的总和&#xff0c;再对两个重复数组所组成的新数组上使用 不定长的滑动窗口 来求得满足目标的最小长度。 class Solution { public:int minSizeSubarray(vector<int>…...

项目经理每天,每周,每月的工作清单

很多不懂项目管理的伙伴问&#xff0c;项目经理每天每周每个月的工作是什么呢&#xff1f; 仿佛他们什么都管&#xff0c;但是又没有具体的产出&#xff0c;但是每天看他们比谁都忙&#xff0c;其实很简单&#xff0c;项目中的每个环节负责具体的事情&#xff0c;但是每个环节…...

Java —— 运算符

目录 1. 什么是运算符 2. 算术运算符 2.1 基本四则运算符: 加减乘除模( - * / %) 2.2 增量运算符 - * %与 自增/自减运算符 -- 3. 关系运算符 4. 逻辑运算符 4.1 逻辑与 && 4.2 逻辑或|| 4.3 逻辑非 ! 4.4 短路求值 5. 位运算符 5.1 按位与 & 5.2 按位或 5.3 按位…...

【C++ 中的友元函数:解密其神秘面纱】

友元函数&#xff0c;作为C中一个重要但常常被误解的概念&#xff0c;经常让初学者感到困惑。本文将带您逐步了解友元函数的含义、用途以及如何正确使用它们。 什么是友元函数&#xff1f; 在C中&#xff0c;友元函数是一种特殊的函数&#xff0c;它允许某个类或类的成员函数…...

YOLOv8涨点技巧:手把手教程,注意力机制如何在不同数据集上实现涨点的工作,内涵多种网络改进方法

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文独家改进&#xff1a;手把手教程&#xff0c;解决注意力机制引入到YOLOv8在自己数据集不涨点的问题点&#xff0c;本文提供五种改进方法来解决此问题&#xff1b; ContextAggregation | 亲测在血细胞检测项目中涨点&#xff0c;…...

牛客:FZ12 牛牛的顺时针遍历

FZ12 牛牛的顺时针遍历 文章目录 FZ12 牛牛的顺时针遍历题目描述题解思路题解代码 题目描述 题解思路 通过一个变量来记录当前方向&#xff0c;遍历矩阵&#xff0c;每次遍历一条边&#xff0c;将该边的信息加入到结果中 题解代码 func spiralOrder(matrix [][]int) []int {…...

函数防抖(javaScript)

防抖说明 &#xff08;1&#xff09;防抖的目的&#xff1a; 当多次执行某一个动作的时候&#xff0c;限制函数调用的次数&#xff0c;节约资源。 &#xff08;2&#xff09;防抖的概念&#xff1a; 函数防抖&#xff08;debounce&#xff09;&#xff1a;就是指触发事件后&…...

日常学习记录随笔-redis实战

redis的持久化&#xff08;rdb,aof,混合持久化&#xff09; redis的主从架构以及redis的哨兵架构 redis的clusterredis 是要做持久化的&#xff0c;一般用redis会把数据放到缓存中为了提升系统的性能 如果redis没有持久化&#xff0c;重启的化数据就会丢失&#xff0c;所有的请…...

MySQL事务MVCC详解

一、概述 MVCC (MultiVersion Concurrency Control) 叫做多版本并发控制机制。主要是通过数据多版本来实现读-写分离&#xff0c;做到即使有读写冲突时&#xff0c;也能做到不加锁&#xff0c;非阻塞并发读&#xff0c;从而提高数据库并发性能。 MVCC只在已提交读&#xff08…...

SQL RDBMS 概念

SQL RDBMS 概念 RDBMS是关系数据库管理系统(Relational Database Management System)的缩写。 RDBMS是SQL的基础&#xff0c;也是所有现代数据库系统(如MS SQL Server、IBMDB2、Oracle、MySQL和MicrosoftAccess)的基础。 关系数据库管理系统(Relational Database Management Sy…...

onlyoffice的介绍搭建、集成过程。Windows、Linux

文章目录 什么是onlyoffice功能系统要求安装必备组件 windows搭建资源下载安装数据库onlyoffice安装测试 Linux搭建dockerdocker-compose 项目中用到的技术&#xff0c;做个笔记哈~ 什么是onlyoffice 在本地服务器上安装ONLYOFFICE Docs Community Edition Community Edition…...

37. 解数独

编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考示例图&#xff09; 数独部分空…...

git cherry-pick 合并某次提交

一、无冲突的情况 1、合并其它分支某次提交 切换到主分支&#xff0c;想把其他分支的某次commit修改 合并到主分支上&#xff0c; 可以用 git cherry-pick 命令 比如&#xff0c;其它分支&#xff0c;某次提交的commit Hash 是30e48158badc39801f1ce3cb375a07b872d6f220 &a…...

【面试HOT100】子串普通数组矩阵

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于LeetCodeHot100进行的&#xff0c;每个知识点的修正和深入主要参考…...

XPSpeak软件教程-科学指南针

在做X 射线光电子能谱(XPS)测试时&#xff0c;科学指南针检测平台工作人员在与很多同学沟通中了解到&#xff0c;好多同学仅仅是通过文献或者师兄师姐的推荐对XPS测试有了解&#xff0c;但是对于其软件操作还属于小白阶段&#xff0c;针对此&#xff0c;科学指南针检测平台团队…...

NLP算法面经 | 腾讯 VS 美团

作者 | 曾同学 编辑 | NewBeeNLP 面试锦囊之面经分享系列&#xff0c;持续更新中 后台回复『面试』加入讨论组交流噢 lz从3月初脚因打球扭伤了开始&#xff0c;投递简历&#xff0c;接二连三的面试鞭尸又面试&#xff0c;昨天才终于上岸了&#xff0c;分享经验~ 腾讯PCG看点&…...

【广州华锐互动】塔吊多人安拆VR互动培训系统

塔吊多人安拆VR互动培训系统由广州华锐互动制作&#xff0c;是一种基于VR技术的模拟实训系统&#xff0c;专门用于培训塔吊驾驶员和操作员。 在现实生活中&#xff0c;塔吊操作具有一定的危险性&#xff0c;尤其是在培训过程中容易发生意外。而使用VR互动实训系统&#xff0c;学…...

Linux性能优化--性能工具:特定进程内存

5.0 概述 本章介绍的工具使你能诊断应用程序与内存子系统之间的交互&#xff0c;该子系统由Linux内核和CPU管理。由于内存子系统的不同层次在性能上有数量级的差异&#xff0c;因此&#xff0c;修复应用程序使其有效地使用内存子系统会对程序性能产生巨大的影响。 阅读本章后&…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

idea大量爆红问题解决

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

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...