[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题 小球角色,执行以下程序…...
终极指南:5步将S905L3-B电视盒子刷成Armbian服务器
终极指南:5步将S905L3-B电视盒子刷成Armbian服务器 【免费下载链接】amlogic-s9xxx-armbian Supports running Armbian on Amlogic, Allwinner, and Rockchip devices. Support a311d, s922x, s905x3, s905x2, s912, s905d, s905x, s905w, s905, s905l, rk3588, rk3…...
告别网络延迟!AutoGLM-Phone-9B本地化部署实战,手机也能流畅对话AI
告别网络延迟!AutoGLM-Phone-9B本地化部署实战,手机也能流畅对话AI 1. AutoGLM-Phone-9B简介与核心优势 1.1 专为移动端设计的轻量级大模型 AutoGLM-Phone-9B是一款革命性的多模态大语言模型,专为移动设备和边缘计算场景优化。与传统的云端…...
终极指南:gallery本地AI模型平台的架构演进与技术发展历程
终极指南:gallery本地AI模型平台的架构演进与技术发展历程 【免费下载链接】gallery A gallery that showcases on-device ML/GenAI use cases and allows people to try and use models locally. 项目地址: https://gitcode.com/GitHub_Trending/gallery44/galle…...
拯救你的网站兼容性:手把手教你用heic2any解决苹果图片上传问题
苹果用户图片上传难题的终极解决方案:前端HEIC转换实战指南 你是否遇到过这样的场景:精心设计的网站上传功能,在苹果用户面前却频频报错?后台服务器不断收到无法识别的图片格式,而用户则抱怨"明明能拍照片却上传…...
实战应用:基于快马打造社交媒体稀有符号昵称生成器
今天想和大家分享一个特别实用的工具开发过程——用InsCode(快马)平台快速搭建社交媒体稀有符号昵称生成器。作为一个经常混迹各种社交平台的用户,我发现在微信、微博、游戏里想取个与众不同的昵称实在太难了,常规字符根本不够炫酷,而手动组合…...
TQVaultAE:3大突破彻底解放《泰坦之旅》装备管理
TQVaultAE:3大突破彻底解放《泰坦之旅》装备管理 【免费下载链接】TQVaultAE Extra bank space for Titan Quest Anniversary Edition 项目地址: https://gitcode.com/gh_mirrors/tq/TQVaultAE 在《泰坦之旅》的冒险旅程中,每个玩家都曾面临装备管…...
SenseVoice-small轻量优势:模型加载时间<2秒,首字响应<800ms
SenseVoice-small轻量优势:模型加载时间<2秒,首字响应<800ms 1. 引言:当语音识别遇上“秒开”体验 想象一下这个场景:你正在一个网络信号极差的山区,或者在一台没有独立显卡的旧电脑上&#x…...
DAMOYOLO-S模型蒸馏实战:将大模型知识迁移至轻量模型
DAMOYOLO-S模型蒸馏实战:将大模型知识迁移至轻量模型 你是不是也遇到过这样的烦恼?好不容易训练出一个精度很高的目标检测模型,比如DAMOYOLO-S,效果确实不错,但模型体积大、计算慢,想把它放到手机或者边缘…...
AI+经济学:当因果推断遇上强化学习,如何重塑政策与市场?
AI经济学:当因果推断遇上强化学习,如何重塑政策与市场?当经济学家还在为模型的假设争论不休时,AI已经学会了从数据洪流中直接“阅读”经济的脉搏。这不是替代,而是一场工具箱的全面升级。引言 在数字经济时代ÿ…...
OpenClaw本地部署指南:千问3.5-9B接口配置与调试技巧
OpenClaw本地部署指南:千问3.5-9B接口配置与调试技巧 1. 为什么选择OpenClaw千问3.5-9B组合 去年我在尝试自动化处理日常工作报告时,发现市面上的RPA工具要么功能臃肿,要么需要将数据上传到云端处理。直到遇到OpenClaw这个开源框架…...
