当前位置: 首页 > 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;修复应用程序使其有效地使用内存子系统会对程序性能产生巨大的影响。 阅读本章后&…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...

轻量安全的密码管理工具Vaultwarden

一、Vaultwarden概述 Vaultwarden主要作用是提供一个自托管的密码管理器服务。它是Bitwarden密码管理器的第三方轻量版&#xff0c;由国外开发者在Bitwarden的基础上&#xff0c;采用Rust语言重写而成。 &#xff08;一&#xff09;Vaultwarden镜像的作用及特点 轻量级与高性…...

【R语言编程——数据调用】

这里写自定义目录标题 可用库及数据集外部数据导入方法查看数据集信息 在R语言中&#xff0c;有多个库支持调用内置数据集或外部数据&#xff0c;包括studentdata等教学或示例数据集。以下是常见的库和方法&#xff1a; 可用库及数据集 openintro库 该库包含多个教学数据集&a…...

Redis:常用数据结构 单线程模型

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;Redis &#x1f525; 常用数据结构 &#x1f433; Redis 当中常用的数据结构如下所示&#xff1a; Redis 在底层实现上述数据结构的过程中&#xff0c;会在源码的角度上对于上述的内容进行特定的…...