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

【单链表算法实战】解锁数据结构核心谜题——相交链表

题目如下:

在这里插入图片描述

解题过程如下:

相交链表只可以在中间任意位置/头/尾结点相交,如下图:

在这里插入图片描述

一个next指针只能指向一块地址,所以不会出现这种情况:
在这里插入图片描述

在返回相交链表的起始结点之前先要判断两个链表是否相交,分析下列两种方法是否可行?

  1. 遍历两个链表,判断结点(地址)是否相同。如果像示例1一样,两个链表的长度不等,代码运行结果就是两个链表不会相交,这与事实恰恰相反。所以这个方法不可行:
    在这里插入图片描述

  2. 看两个链表的尾结点(地址)是否相同。参考相交链表的三种情况,尾结点相同那么两个链表就一定相交。

那么怎么返回相交链表的起始结点呢?

思路:求两个链表的长度,长链表先走长度差步,长短链表遍历比较结点的地址是否相同。

完整代码如下:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//求两个链表的长度ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0;int sizeB = 0;while (pa){++sizeA;pa = pa->next;}while (pb){++sizeB;pb = pb->next;}//长链表先走长度差(gap)步int gap = abs(sizeA - sizeB);ListNode* shortList = headA;ListNode* longList = headB;//假设B是长链表if (sizeA > sizeB){shortList = headB;longList = headA;}while (gap--){longList = longList->next;}//长短链表遍历结点的地址是否相同while (longList) //等同于shortList != NULL{if (longList == shortList)return longList;longList = longList->next;shortList = shortList->next;}return NULL;
}

abs()函数用于求绝对值:
在这里插入图片描述

相关文章:

【单链表算法实战】解锁数据结构核心谜题——相交链表

题目如下: 解题过程如下: 相交链表只可以在中间任意位置/头/尾结点相交,如下图: 一个next指针只能指向一块地址,所以不会出现这种情况: 在返回相交链表的起始结点之前先要判断两个链表是否相交&#xff0…...

Crewai框架添加日志功能

一开始看官方文档以为要用callback这个注释在一个自定义函数上输出日志,结果弄半天都没有结果,最后发已经有现成的方法了(一开始搜log都没搜到这个方法) 只要添加这个output_log_file配置参数即可,由于我的项目只有一…...

【2025年数学建模美赛E题】(农业生态系统)完整解析+模型代码+论文

生态共生与数值模拟:生态系统模型的物种种群动态研究 摘要1Introduction1.1Problem Background1.2Restatement of the Problem1.3Our Work 2 Assumptions and Justifications3 Notations4 模型的建立与求解4.1 农业生态系统模型的建立与求解4.1.1 模型建立4.1.2求解…...

Linux(Centos、Ubuntu) 系统安装jenkins服务

该文章手把手演示在Linux系统下如何安装jenkins服务、并自定义jenkins数据文件位置、以及jenkins如何设置国内镜像源加速,解决插件下载失败问题 安装方式:war包安装 阿里云提供的war下载源地址:https://mirrors.aliyun.com/jenkins/war/?s…...

2013年蓝桥杯第四届CC++大学B组真题及代码

目录 1A:高斯日记(日期计算) 2B:马虎的算式(暴力模拟) 3C:第39级台阶(dfs或dp) 4D:黄金连分数(递推大数运算) 5E:前缀…...

TDengine 做为 FLINK 数据源技术参考手册

Apache Flink 是一款由 Apache 软件基金会支持的开源分布式流批一体化处理框架,可用于流处理、批处理、复杂事件处理、实时数据仓库构建及为机器学习提供实时数据支持等诸多大数据处理场景。与此同时,Flink 拥有丰富的连接器与各类工具,可对接…...

21.2、网络设备安全机制与实现技术

目录 网络设备安全机制与实现技术 - 认证技术网络设备安全机制与实现技术 - 访问控制网络设备安全机制与实现技术 - 信息加密网络设备安全机制与实现技术 - 安全通信网络设备安全机制与实现技术 - 日志审计网络设备安全机制与实现技术 - 安全增强网络设备安全机制与实现技术 - …...

数据结构:二叉树—面试题(二)

1、二叉树的最近公共祖先 习题链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 描述: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点…...

OFD、PDF 电子签章系统处理流程

在C#中实现电子签章系统的处理流程,可以参考以下步骤和技术实现: 1. 电子签章系统的基本流程 电子签章系统的核心流程包括以下几个步骤: 密钥生成:生成公钥和私钥对,私钥由签章人保管,公钥用于验证签名。…...

分布式微服务系统简述

distributed microservice 分布式与微服务的定义及关系;分布式微服务架构里的各组件,如:配置中心、服务注册/发现、服务网关、负载均衡器、限流降级、断路器、服务调用、分布式事务等;spring cloud 介绍及实现案例,如…...

【Linux】列出所有连接的 WiFi 网络的密码

【Linux】列出所有连接的 WiFi 网络的密码 终端输入 sudo grep psk /etc/NetworkManager/system-connections/*会列出所有连接过 Wifi 的信息,格式类似 /etc/NetworkManager/system-connections/AAAAA.nmconnection:pskBBBBBAAAAA 是 SSID,BBBBB 是对…...

电脑无法开机,重装系统后没有驱动且驱动安装失败

电脑无法开机,重装系统后没有驱动且驱动安装失败 前几天电脑突然坏了,电脑卡住后,强制关机,再开机后开机马上就关机。尝试无数次开机后失败,进入BIOS界面,发现已经没有Windows系统了。重新安装系统后&…...

基于SpringBoot格式化实体的时间类型以及静态注入依赖

一. 场景描述 在进行前后端交互时,发现实体的LocalDateTime返回的格式是这样的: 这不符合我们日常习惯的格式 “年-月-日 时:分:秒”,于是上网学习了前辈 励碼的文章SSM项目中LocalDateTime格式化最佳实践_localdatetime 格式化-CSDN博客解决…...

技术总结:FPGA基于GTX+RIFFA架构实现多功能SDI视频转PCIE采集卡设计方案

目录 1、前言工程概述免责声明 3、详细设计方案设计框图SDI 输入设备Gv8601a 均衡器GTX 解串与串化SMPTE SD/HD/3G SDI IP核BT1120转RGBFDMA图像缓存RIFFA用户数据控制RIFFA架构详解Xilinx 7 Series Integrated Block for PCI ExpressRIFFA驱动及其安装QT上位机HDMI输出RGB转BT…...

Flink读写Kafka(Table API)

前面(Flink读写Kafka(DataStream API)_flink kafka scram-CSDN博客)我们已经讲解了使用DataStream API来读取Kafka,在这里继续讲解下使用Table API来读取Kafka,和前面一样也是引入相同的依赖即可。 <dependency> <groupId>org.apache.flink</groupId&…...

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】1.2 ndarray解剖课:多维数组的底层实现

1.2 《ndarray解剖课&#xff1a;多维数组的底层实现》 内容介绍 NumPy 的 ndarray 是其核心数据结构&#xff0c;用于高效处理多维数组。在这篇文章中&#xff0c;我们将深入解析 ndarray 的底层实现&#xff0c;探讨其内存结构、维度、数据类型、步长等关键概念&#xff0c…...

冯诺依曼架构和哈佛架构的主要区别?

冯诺依曼架构&#xff08;Von Neumann Architecture&#xff09;和哈佛架构&#xff08;Harvard Architecture&#xff09;是两种计算机体系结构&#xff0c;它们在存储器组织、指令处理和数据存取等方面有明显的不同。以下是它们的主要区别&#xff1a; 1.存储器结构 冯诺依曼…...

Gurobi基础语法之字典

Python中的字典&#xff1a;dict 我们先来介绍一下Python语法中的 dict 类型, 字典中可以通过任意键值来对数据进行映射&#xff0c;任何无法修改的python对象都可以当作键值来使用&#xff0c;这些无法修改的Python对象包括&#xff1a;整数(比如&#xff1a;1)&#xff0c;浮…...

ceph新增节点,OSD设备,标签管理(二)

一、访问客户端集群方式 方式一: 使用cephadm shell交互式配置 [rootceph141 ~]# cephadm shell # 注意&#xff0c;此命令会启动一个新的容器&#xff0c;运行玩后会退出&#xff01; Inferring fsid c153209c-d8a0-11ef-a0ed-bdb84668ed01 Inferring config /var/lib/ce…...

利用metaGPT多智能体框架实现智能体-2

1.一些帮助理解的概念 智能体 在MetaGPT看来&#xff0c;可以将智能体想象成环境中的数字人&#xff0c;其中 智能体 大语言模型&#xff08;LLM&#xff09; 观察 思考 行动 记忆 这个公式概括了智能体的功能本质。为了理解每个组成部分&#xff0c;让我们将其与人类进…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

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

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

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...