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

L22.【LeetCode笔记】相交链表(新版)

目录

1.题目

代码模板

2.分析

​编辑 算法误区

正确方法1

但不能通过所有的测试用例

修改后

提交结果 

正确方法2 

节省代码的技巧


1.题目

https://leetcode.cn/problems/3u1WK4/description/

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

图示两个链表在节点 c1 开始相交

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

提示:

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点,intersectVal 为 0
  • 如果 listA 和 listB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶:能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?

注意:本题与主站 160 题相同:160. 相交链表 - 力扣(LeetCode)

代码模板

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{   
}

2.分析

旧版分析见L10.【LeetCode笔记】环形链表(判断链表中是否有环)(旧版)文章

读题可知,对于两个链表相交可能有以下三种情况

中间节点相交

头结点相交(下图为A链表的中间节点和B链表的头节点相交)

尾节点相交

但绝对不存在“X”形的相交情况,一个节点只能有一个next指针

 算法误区

设两个指针p1和p2分别从A和B链表的头节点出发,不能通过p1->val==p2->val来判断到达了相交节点,会对不相交的链表造成误判

正确方法1

将A链表的每个节点的地址和B链表的所有节点的地址进行比较,如果相等则可求出相交节点的地址

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * pA=headA;struct ListNode * pB=headB;while(pA!=pB){if (pB==NULL){pB=headB;pA=pA->next;}if (pA==NULL)return NULL;pB=pB->next;}return pA;
}

但不能通过所有的测试用例

原因:pB->next==NULL,因此pB=pB->next为pB=NULL->next,不合法,尾部相交会出问题

  

修改后

 其实只需要交换下判断的顺序即可

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * pA=headA;struct ListNode * pB=headB;while(pA!=pB){if (pA==NULL)return NULL;pB=pB->next;if (pB==NULL){pB=headB;pA=pA->next;}}return pA;
}

 

提交结果 

 这种方法时间复杂度为O(M*N),不推荐使用 

正确方法2 

双指针算法时间复杂度为O(N),参见L7.【LeetCode笔记】相交链表(旧版)

其实双指针的代码还可以写的更简洁些

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode * tailA=headA;struct ListNode * tailB=headB;int lenA=1;int lenB=1;//求A和B链表的长度while (tailA->next){tailA=tailA->next;lenA++;}while (tailB->next){tailB=tailB->next;lenB++;}//两个while循环结束后,tailA和tailB分别指向各自链表的尾部节点if (tailA!=tailB)return NULL;//非尾部相交,返回NULL//头部相交和中间相交的情况int distance=abs(lenA-lenB);//假设A链表为长链表,B链表为短链表struct ListNode * longlist=headA;struct ListNode * shortlist=headB;//假设不成立再更正,节省代码if (lenA<lenB){longlist=headB;shortlist=headA;} while (distance--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

节省代码的技巧

假设A链表为长链表(longlis接收),B链表为短链表(shortlist接收),如果假设不成立,再更正(修改longlist和shortlist),这样就不用做if{...}else{...}了,减少重复代码

相关文章:

L22.【LeetCode笔记】相交链表(新版)

目录 1.题目 代码模板 2.分析 ​编辑 算法误区 正确方法1 但不能通过所有的测试用例 修改后 提交结果 正确方法2 节省代码的技巧 1.题目 https://leetcode.cn/problems/3u1WK4/description/ 给定两个单链表的头节点 headA 和 headB &#xff0c;请找出并返回两个单…...

智能时代网络空间认知安全新观察

文章目录 前言一、历史上的四次认知革命二、人工智能革命掀起认知安全新浪潮三、人工智能技术塑造认知安全新范式四、人工智能治理应对认知安全新思考 前言 12月5日&#xff0c;在2024第三届北外滩网络安全论坛上以“智能时代网络空间认知安全新观察”为主题作主旨演讲&#x…...

游戏如何应对模拟器作弊

模拟器是指能在PC端模拟出安卓手机系统的软件&#xff0c;市面上比较常见的安卓模拟器有&#xff1a;雷电模拟器、MuMu模拟器、夜神模拟器等。 市面上常见的模拟器 模拟器既可以节省手机内存空间&#xff0c;避免长时间玩游戏手机发烫发热的尴尬&#xff0c;也可以用键盘鼠标对…...

c++ 判断一个 IP 地址(可能是 IPv6 或 IPv4)是否属于特定范围

在 C 中&#xff0c;判断一个 IP 地址&#xff08;可能是 IPv6 或 IPv4&#xff09;是否属于特定范围时&#xff0c;需要考虑两种不同的地址格式和它们的范围比较。IPv6 和 IPv4 地址结构完全不同&#xff0c;因此需要分别处理这两种地址类型。 实现思路&#xff1a; 识别 IP…...

计算机视觉——相机标定(Camera Calibration)

文章目录 1. 简介2. 原理3. 相机模型3.1 四大坐标系3.2 坐标系间的转换关系3.2.1 世界坐标系到相机坐标系3.2.2 相机坐标系到图像坐标系3.2.3 像素坐标系转换为图像坐标系3.2.4 世界坐标转换为像素坐标 3.3 畸变3.3.1 畸变类型3.3.1.1 径向畸变&#xff08;Radial Distortion&a…...

【qt环境配置】windows下的qt与vs工具集安装\版本对应关系

vs工具集安装通过vs的在线安装器勾选工具集即可 工具包下载路径&#xff1a;https://www.microsoft.com/zh-cn/download/details.aspx?id40784 配置工具集在qt中可以自动扫描到 《正确在 Windows 上配置 MSVC(2019) 作为 Qt 编译器》https://b3logfile.com/pdf/article/15922…...

GitHub使用

太久不用GitHub发现自己又有些不会了&#xff0c;突发奇想为何不把每次看到的有指导意义的博客收录一下以便下次查阅呢 如何上传文件夹到GitHub上&#xff08;配图详解&#xff09;&#xff1f;_github上傳資料夾-CSDN博客 github上如何删除自己的仓库_github删除仓库-CSDN博…...

元宇宙时代的社交平台:Facebook的愿景与实践

随着科技的不断进步&#xff0c;元宇宙&#xff08;Metaverse&#xff09;这一概念逐渐走进了人们的视野。作为全球最大的社交平台之一&#xff0c;Facebook&#xff08;现Meta&#xff09;在这场元宇宙革命中扮演着重要角色。Meta不仅在不断扩展其社交平台的边界&#xff0c;还…...

vue2中各种钩子函数的总结以及使用场景

在 Vue 2 中&#xff0c;生命周期钩子函数是 Vue 实例在不同阶段自动调用的函数。这些钩子允许开发者在组件的创建、更新和销毁的特定时刻插入自定义逻辑。以下是 Vue 2 中的各种生命周期钩子函数的总结及其使用场景。 生命周期钩子函数总结 1、beforeCreate 调用时机&#…...

软件架构:从传统单体到现代微服务的技术演变

1.引言 在软件开发中&#xff0c;架构设计不仅仅是程序员的技术任务&#xff0c;它更是一个项目成功的关键。无论是小型应用还是大型分布式系统&#xff0c;软件架构都直接影响着系统的可维护性、可扩展性、性能和稳定性。理解软件架构的必要性&#xff0c;能够帮助开发人员做…...

git新建远程分支后,无法切换

git remote # 列出所有远程主机 git remote update origin --prune # 更新远程主机origin 整理分支 git branch -r # 列出远程分支 git branch -vv # 查看本地分支和远程分支对应关系 git checkout -b gpf origin/gpf # 新建本地分支gpf与远程gpf分支相关…...

【SpringBoot】31 Session + Redis 实战

Gitee https://gitee.com/Lin_DH/system 介绍 【SpringBoot】30 Cookie、Session、Token https://blog.csdn.net/weixin_44088274/article/details/144241595 背景 Spring Session 是 Spring 的一个子项目&#xff0c;它提供了一种管理用户会话信息的方法&#xff0c;无论…...

在Windows环境下的rknn-toolkit环境搭建

首先安装好conda&#xff0c;我是用的是anaconda&#xff0c;miniconda也可以。 下载rknn_toolkit的轮子。可以直接在瑞芯微的git仓库中下载&#xff0c;地址为&#xff1a;github.com/rockchip-linux/rknn-toolkit/releases。我这里下载的是1.7.5版本的。选择rknn-toolkit-v1.…...

Facebook广告突然无消耗?原因解析与解决方案。

在Facebook广告投放中&#xff0c;广告突然无消耗是很多广告主都会遇到的难题。这种情况不仅浪费时间&#xff0c;还可能导致营销活动停滞&#xff0c;影响业务发展。那么&#xff0c;广告无消耗的原因是什么&#xff1f;又该如何解决呢&#xff1f; 一、Facebook广告无消耗的…...

Rabbitmq 镜像队列

RabbitMQ 支持高可用性队列&#xff08;HA Queues&#xff09;&#xff0c;可以在多个节点之间复制队列&#xff0c;确保即使某个节点失败&#xff0c;消息仍然可用。将 RabbitMQ 部署为集群&#xff0c;确保高可用性和负载均衡。 RabbitMQ 的镜像队列集群&#xff08;Mirrore…...

TensorBoard

1、TensorFlow的TensorBoard TensorBoard是TensorFlow的一个组件&#xff0c;它提供了一个交互式的界面&#xff0c;用于可视化TensorFlow程序的训练过程和模型结构。 使用TensorBoard&#xff0c;你可以&#xff1a; 可视化训练过程中的各种指标&#xff0c;如损失函数、准…...

运维实战:K8s 上的 Doris 高可用集群最佳实践

今天我们将深入探讨&#xff1a;&#xff1a;如何在 K8s 集群上部署 Compute storage coupled&#xff08;存算耦合&#xff09; 模式的 Doris 高可用集群&#xff1f; 本文&#xff0c;我将为您提供一份全面的实战指南&#xff0c;逐步引导您完成以下关键任务&#xff1a; 配…...

2024.12.5——攻防世界Training-WWW-Robots攻防世界baby_web

2024.12.5—攻防世界Training-WWW-Robots 知识点&#xff1a;robots协议 dirsearch工具 本题与第一道Robots协议十分类似&#xff0c;不做wp解析 大致步骤&#xff1a; step 1 打开靶机&#xff0c;发现是robots协议相关 step 2 用dirsearch进行扫描目录 step 3 url传参r…...

当 Nginx 出现连接超时问题,如何排查?

文章目录 当 Nginx 出现连接超时问题&#xff0c;如何排查&#xff1f; 一、了解 Nginx 连接超时的基本概念二、可能导致 Nginx 连接超时的原因 &#xff08;一&#xff09;服务器负载过高&#xff08;二&#xff09;上游服务响应缓慢&#xff08;三&#xff09;网络问题&…...

vue2 项目中实现动态代理,服务器上通过nginx部署 实现动态代理

一、前言&&原理 前言&#xff1a;vue2 项目中&#xff0c;请求接口是从表格的当前获取的&#xff0c;也就是接口ip:端口号:路经不确定&#xff0c;要实现点击表格当前行请求对应的接口 实现原理&#xff1a;将实际要请求的ip等信息存在请求头中&#xff0c;用的时候再…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...