[LeetBook]【学习日记】寻找链表相交节点
来源于「Krahets」的《图解算法数据结构》
https://leetcode.cn/leetbook/detail/illustration-of-algorithm/
本题与主站 160 题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
训练计划 V
某教练同时带教两位学员,分别以链表 l1、l2
记录了两套核心肌群训练计划,节点值为训练项目编号。两套计划仅有前半部分热身项目不同,后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点,返回null 。输入说明:
intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
l1 - 第一个训练计划链表
l2 - 第二个训练计划链表
skip1 - 在 l1 中(从头节点开始)跳到交叉节点的节点数
skip2 - 在 l2 中(从头节点开始)跳到交叉节点的节点数
程序将根据这些输入创建链式数据结构,并将两个头节点 head1 和 head2
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被视作正确答案 。示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA
= 2, skipB = 3 输出:Reference of the node with value = 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 输出:Reference of the node with value = 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 解释:两套计划完全不同,返回 null。从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。注意:
如果两个链表没有交点,返回 null. 在返回结果后,两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n)
时间复杂度,且仅用 O(1) 内存。 本题与主站 160题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fvoq2/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
暴力解法
- 利用 unordered_set 这种数据结构存储 A 链表节点,由于这种结构的 find 效率很高,故可在其中直接检索是否存在 B 链表的节点,存在则为交点
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> addrOfNode;while(headA){addrOfNode.insert(headA);headA = headA->next; }while(headB){if(addrOfNode.find(headB) != addrOfNode.end()){return headB;}else{headB = headB->next;}}return nullptr;}
};
双指针解法

- 设置指针 a 和 b 分别遍历两条链表后再遍历对方那一条链表,指针相遇有a+(b−c)=b+(a−c),即为交点
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *a = headA, *b = headB;while(a != b){a = a ? a->next : headB;b = b ? b->next : headA;}return a;}
};
相关文章:
[LeetBook]【学习日记】寻找链表相交节点
来源于「Krahets」的《图解算法数据结构》 https://leetcode.cn/leetbook/detail/illustration-of-algorithm/ 本题与主站 160 题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/ 训练计划 V 某教练同时带教两位学员,分别以…...
【Python】OpenCV-使用ResNet50进行图像分类
使用ResNet50进行图像分类 如何使用ResNet50模型对图像进行分类。 import os import cv2 import numpy as np from tensorflow.keras.applications.resnet50 import ResNet50, preprocess_input, decode_predictions from tensorflow.keras.preprocessing import image# 设置…...
TypeError: `dumps_kwargs` keyword arguments are no longer supported
TypeError: dumps_kwargs keyword arguments are no longer supported 1. 问题描述2. 解决方法 1. 问题描述 使用 FastChat 启动私有大语言模型,通过一些 UI 工具进行访问时,报以下错误。 略 2024-02-29 09:26:14 | ERROR | stderr | yield f"…...
设计模式学习笔记 - 设计原则 - 3.里氏替换原则,它和多态的区别是什么?
前言 今天来学习 SOLID 中的 L:里氏替换原则。它的英文翻译是 Liskov Substitution Principle,缩写为 LSP。 英文原话是: Functions that use points of references of base classes must be able to use objects of derived classes withou…...
java实现图片转pdf,并通过流的方式进行下载(前后端分离)
首先需要导入相关依赖,由于具体依赖本人也不是记得很清楚了,所以简短的说一下。 iText:PDF 操作库,用于创建和操作 PDF 文件。可通过 Maven 或 Gradle 引入 iText 依赖。 MultipartFile:Spring 框架中处理文件上传的类…...
如何系统的学习Python——Python的基本语法
学习Python的基本语法是入门的第一步,以下是一些常见的基本语法概念: 注释: 用#符号来添加单行注释,或使用三引号(或""")来添加多行注释。 # 这是一个单行注释 这是 多行 注释 变量和数据类型: 变量用…...
相机,棱镜和光场
一、成像方法 Imaging Synthesis Capture 1.Synthesis(图形学上)合成:比如之前学过的光线追踪或者光栅化 2.Capture(捕捉):把真实世界存在的东西捕捉成为照片 二、相机 1.小孔成像 利用小孔成像的相…...
【图像版权】论文阅读:CRMW 图像隐写术+压缩算法
不可见水印 前言背景介绍ai大模型水印生成产物不可见水印CRMW 在保护深度神经网络模型知识产权方面与现有防御机制有何不同?使用图像隐写术和压缩算法为神经网络模型生成水印数据集有哪些优势?特征一致性训练如何发挥作用,将水印数据集嵌入到…...
代码随想录算法训练营第31天—贪心算法05 | ● 435. 无重叠区间 ● *763.划分字母区间 ● *56. 合并区间
435. 无重叠区间 https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html 考点 贪心算法重叠区间 我的思路 先按照区间左坐标进行排序,方便后续处理进行for循环,循环范围是0到倒数第二个元素如果当前区间和下一区间重叠…...
2024《》
vue-cli到哪做了那些事 vue-cli是vue.js的脚手架,用于自动生成vue.jswebpack的项目模板,快速搭建Vue.js项目。 vue cli内置了webpack的一些功能,这些是用webpack打包时需要我们自己配置的,例如: 1.ES6代码转换成ES5代…...
【Web】Java反序列化之从CC3看TemplatesImpl的利用
目录 关于TemplatesImpl 关于TemplatesImpl加载字节码 CC3链分析 纯CC3demo 根据CC3改CC6 关于TemplatesImpl TemplatesImpl 是 Java 中的一个类,通常与 Java 反序列化漏洞相关的攻击中被使用。该类位于 Java 标准库中的 javax.xml.transform 包下。 在 Java…...
【Elasticsearch索引】Recovery恢复索引
文章目录 索引恢复恢复列表获取恢复信息响应详细信息正在进行的恢复响应解析高级设置 本地分片恢复事务日志 索引恢复 索引恢复提供了对正在进行的索引分片恢复的洞察。恢复状态可以针对特定的索引报告,也可以在集群范围内报告。 恢复列表 recovery命令是索引分片…...
如何在 Linux 中快速清空文件而不删除它们?
在Linux系统中,清空文件而不删除它们是一种常见的需求,特别是在需要保留文件结构或权限的情况下。本文将详细介绍如何在Linux环境中快速清空文件内容的多种方法,以及每种方法的优缺点。清空文件通常涉及到文件内容的擦除,但并不涉…...
SpringBoot 配置文件${variable:default}用法
${variable:default}用法,variable是变量名,default是默认值。如果配置文件中未指定该变量的值,则会使用默认值来替代。 解释代码: ip: ${NACOS_IP:nacos.ip} 该yaml函数是一个配置项,用来指定Nacos服务器的IP地…...
CUDA学习笔记02:测试程序hello world
参考资料 Win10下在VS2019中配置使用CUDA进行加速的C项目 (配置.h文件,.dll以及.lib文件等)_vs2019 cuda-CSDN博客 配置流程 1. 新建一个一般的项目 2. 项目建好后,在项目里添加.cu测试文件 测试的.cu文件命名为cuda_utils.cu&…...
2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题
2023年第十四届蓝桥杯大赛软件类省赛C/C大学A组部分真题和题解分享 文章目录 蓝桥杯2023年第十四届省赛真题-平方差思路题解 蓝桥杯2023年第十四届省赛真题-更小的数思路题解 蓝桥杯2023年第十四届省赛真题-颜色平衡树思路题解 蓝桥杯2023年第十四届省赛真题-买瓜思路题解 蓝桥…...
项目部署发布
目录 上传数据库 修改代码中的数据源配置 修改配置文件中的日志级别和日志目录 打包程序 编辑编辑 上传程序 查看进程是否在运行 以及端口 云服务器开放端口(项目所需要的端口) 上传数据库 通过xshell控制服务器 创建目录 mkdir bit_forum 然后进入该目录 查看路…...
MATLAB环境下基于离散小波变换的心电信号伪影去除及PQRST波检测
可穿戴个人健康监护系统被广泛认为是下一代健康监护技术的核心解决方案。监护设备不断地感知、获取、分析和存储大量人体在日常活动中的生理数据,为人体的健康状况提供必要的、准确的、集成的和长期的评估和反馈。在心电监测领域,可穿戴传感器具有以下应…...
SwiftUI 在 App 中弹出全局消息横幅(下)
功能需求 在 SwiftUI 开发的 App 界面中,有时我们需要在全局层面向用户展示一些消息: 如上图所示:我们弹出的全局消息横幅位于所有视图之上,这意味这它不会被任何东西所遮挡;而且用户可以点击该横幅关闭它。这是怎么做到的呢? 在本篇博文中,您将学到以下内容 功能需求…...
2023年06月CCF-GESP编程能力等级认证Scratch图形化编程三级真题解析
本文收录于专栏《Scratch等级认证CCF-GESP真题解析》,专栏总目录・点这里 一、单选题(共15题,共30分) 第1题 高级语言编写的程序需要经过以下( )操作,可以生成在计算机上运行的可执行代码。 A:编辑 B:保存 C:调试 D:编译 答案:D 第2题 小球角色,执行以下程序…...
7个实用技巧:用immich实现自托管相册智能管理 | 隐私保护与高效共享指南
7个实用技巧:用immich实现自托管相册智能管理 | 隐私保护与高效共享指南 【免费下载链接】immich High performance self-hosted photo and video management solution. 项目地址: https://gitcode.com/GitHub_Trending/im/immich 你是否曾在数千张照片中艰难…...
IAR开发环境配置:解决Fatal Error[Pe1696]头文件缺失问题
1. 初识Fatal Error[Pe1696]:头文件去哪了? 第一次用IAR开发环境的朋友,十有八九会遇到这个让人抓狂的错误提示:"Fatal Error[Pe1696]: cannot open source file core_cm0plus.h"。这就像你照着菜谱做菜,明明…...
Whisper.cpp 跨平台编译与语音识别实战指南
1. Whisper.cpp 是什么?能做什么? 第一次接触 Whisper.cpp 是在一个语音转文字的需求场景中。当时需要处理大量会议录音,但发现主流的语音识别工具要么需要联网,要么对硬件要求极高。直到发现了这个基于 C 实现的轻量级解决方案&a…...
3分钟掌握ZXPInstaller:Adobe插件安装的革命性解决方案
3分钟掌握ZXPInstaller:Adobe插件安装的革命性解决方案 【免费下载链接】ZXPInstaller Open Source ZXP Installer for Adobe Extensions 项目地址: https://gitcode.com/gh_mirrors/zx/ZXPInstaller 还在为Adobe插件安装而烦恼吗?ZXPInstaller作…...
Seldon Core 2性能调优终极指南:10个关键指标提升推理速度300%
Seldon Core 2性能调优终极指南:10个关键指标提升推理速度300% 【免费下载链接】seldon-core An MLOps framework to package, deploy, monitor and manage thousands of production machine learning models 项目地址: https://gitcode.com/gh_mirrors/se/seldon…...
AI Agent与边缘计算结合:低延迟场景下的智能体部署方案
AI Agent与边缘计算结合:低延迟场景下的智能体部署方案 关键词:AI Agent、边缘计算、低延迟部署、模型压缩、资源调度、隐私计算、多智能体协同 摘要:本文将像给小学生讲“快递柜前置配送奶茶”的故事一样,深入浅出地解释AI Agent和边缘计算是什么、为什么要把它们结合、如…...
保姆级教程:在Ubuntu 20.04上从零搭建宇树Go1机器狗的ROS仿真环境(含Gazebo避坑)
从零构建宇树Go1机器狗的ROS仿真环境:Ubuntu 20.04全流程指南 当四足机器人从实验室走向消费市场,宇树科技的Go1凭借其灵活动作和开源生态迅速成为开发者新宠。但第一次打开Gazebo看到机器狗瘫倒在地时,多数新手都会陷入手足无措的境地——依…...
Qwen3-ForcedAligner-0.6B语音强制对齐实战:基于LLM的时间戳预测
Qwen3-ForcedAligner-0.6B语音强制对齐实战:基于LLM的时间戳预测 1. 引言 你有没有遇到过这样的情况:手里有一段音频和对应的文字稿,想要知道每个词在音频中的具体位置?比如给视频加字幕时,需要精确到每个字的出现时…...
如何通过MobaXterm中文版快速构建一体化远程管理环境
如何通过MobaXterm中文版快速构建一体化远程管理环境 【免费下载链接】Mobaxterm-Chinese Mobaxterm simplified Chinese version. Mobaxterm 的简体中文版. 项目地址: https://gitcode.com/gh_mirrors/mo/Mobaxterm-Chinese 远程管理工具的选择常常让系统管理员和开发者…...
3步搞定精准歌词:LDDC歌词工具全方位解决方案
3步搞定精准歌词:LDDC歌词工具全方位解决方案 【免费下载链接】LDDC 简单易用的精准歌词(逐字歌词/卡拉OK歌词)下载匹配工具|A simple and user-friendly tool for downloading and matching precise lyrics (word-by-word lyrics/Karaoke lyrics) 项目地址: http…...
