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

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...