每日一题(相交链表 )
欢迎大家来我们主页进行指导
LaNzikinh-CSDN博客
160. 相交链表 - 力扣(LeetCode)
给你两个单链表的头节点
headA
和headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回null
。图示两个链表在节点
c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal
- 相交的起始节点的值。如果不存在相交节点,这一值为0
listA
- 第一个链表listB
- 第二个链表skipA
- 在listA
中(从头节点开始)跳到交叉节点的节点数skipB
- 在listB
中(从头节点开始)跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构,并将两个头节点
headA
和headB
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
首先做这个题目有两个核心的关键就是,1.你要判断它是不是相交的。2.它的交点
思路一:暴力求解
依次去A链表中的每个节点跟B链表中的所有节点比较,如果有地址相同的节点,就是相交,第一个相同的就是交点
时间复杂度为O(N^2),非常麻烦,这里就不多说了,我们直接来说思路二
思路二:长度差法
核心:尾结点相同,就是相交否则就不相交,长的链表先走长度差步,再同时走,第一个相同的就是交点
2.1计算长度
先保存两个头结点用来比较长度,因为我遍历完了两个链表,所以把是不是相交一起判断了
//先保存两个头结点用来比较长度
struct ListNode* tailA = headA;
struct ListNode* tailB = headB;
//计算A的长度
int lenA = 1;
while (tailA->next != NULL)
{lenA++;tailA = tailA->next;
}
//计算B的长度
int lenB = 1;
while (tailB->next != NULL)
{lenB++;tailB = tailB->next;
}
//是不是相交一起判断
if (tailA != tailB)
{return NULL;
}
2.2判断那个长?
这个用了一个非常巧妙的办法来写出了如何判断这两个长,因为我不知道这两个最开始到底是谁长
//abs取绝对值
int gap = abs(lenA - lenB);
//先假设A长
struct ListNode* long = headA;
struct ListNode* short = headB;
//在做出判断,如果A短就互换
if (lenA < lenB)
{struct ListNode* long = headB;struct ListNode* short = headA;
}
2.3长的先走,短的在一起走
//长的先走gap步
while (gap--)
{long = long->next;
}
//等长的走完,在一起走,之后返回向遇点就可以了
while (long != short)
{long = long->next;short = short->next;
}
//返回short也可以
return long;
2.4总代码
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{//先保存两个头结点用来比较长度struct ListNode* tailA = headA;struct ListNode* tailB = headB;//计算A的长度int lenA = 1;while (tailA->next != NULL){lenA++;tailA = tailA->next;}//计算B的长度int lenB = 1;while (tailB->next != NULL){lenB++;tailB = tailB->next;}if (tailA != tailB){return NULL;}//abs取绝对值int gap = abs(lenA - lenB);//先假设A长struct ListNode* long = headA;struct ListNode* short = headB;//在做出判断,如果A短就互换if (lenA < lenB){struct ListNode* long = headB;struct ListNode* short = headA;}//长的先走gap步while (gap--){long = long->next;}//等长的走完,在一起走,之后返回向遇点就可以了while (long != short){long = long->next;short = short->next;}//返回short也可以return long;
}
相关文章:

每日一题(相交链表 )
欢迎大家来我们主页进行指导 LaNzikinh-CSDN博客 160. 相交链表 - 力扣(LeetCode) 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节…...
C#WPF控件大全
本文列出WPF控件大全,点击可以进入详情页查看。 列表如下: AccessText用下划线来指定用作访问键的字符。 ActivatingKeyTipEventArgs为 ActivatingKeyTip 事件提供数据。...

好书推荐 《AIGC重塑金融》
作者:林建明 来源:IT 阅读排行榜 本文摘编自《AIGC 重塑金融:AI 大模型驱动的金融变革与实践》,机械工业出版社出版 这是最好的时代,也是最坏的时代。尽管大模型技术在金融领域具有巨大的应用潜力,但其应…...

【Linux】权限理解
权限理解 1. shell命令以及运行原理2. Linux权限的概念3. Linux权限管理3.1 文件访问者的分类(人)3.2 文件类型和访问权限(事物属性)3.2.1 文件类型3.2.2 基本权限 3.3 文件权限值的表示方法3.4 文件访问权限的相关设置方法3.4.1 …...

插入排序、归并排序、堆排序和快速排序的稳定性分析
插入排序、归并排序、堆排序和快速排序的稳定性分析 一、插入排序的稳定性二、归并排序的稳定性三、堆排序的稳定性四、快速排序的稳定性总结 在计算机科学中,排序是将一组数据按照特定顺序进行排列的过程。排序算法的效率和稳定性是评价其优劣的两个重要指标。稳定…...

【pytest、playwright】多账号同时操作
目录 方案实现思路: 方案一: 方案二: 方案实现思路: 依照上图所见,就知道,一个账号是pytest-playwright默认的环境,一个是 账号登录的环境 方案一: 直接上代码: imp…...

软考 系统架构设计师系列知识点之云原生架构设计理论与实践(8)
接前一篇文章:软考 系统架构设计师系列知识点之云原生架构设计理论与实践(7) 所属章节: 第14章. 云原生架构设计理论与实践 第2节 云原生架构内涵 14.2 云原生架构内涵 关于云原生的定义有众多版本,对于云原生架构的…...

【C++】stack、queue和优先级队列
一、前言 二、stack类 2.1 了解stack 2.2 使用stack (1)empty (2)size (3)top (4)push (5)pop 2.3 stack的模拟实现 三、queue类 3.1 了解queue …...

第十三届蓝桥杯国赛真题 Java C 组【原卷】
文章目录 发现宝藏试题 A: 斐波那契与 7试题 B: 小蓝做实验试题 C: 取模试题 D: 内存空间试题 E \mathrm{E} E : 斐波那契数组试题 F: 最大公约数试题 G: 交通信号试题 I: 打折试题 J: 宝石收集 发现宝藏 前些天发现了一个巨牛的人工智能学习网站,通俗易懂&#x…...

docker部署ubuntu
仓库: https://hub.docker.com/search?qUbuntu 拉一个Ubuntu镜像 docker pull ubuntu:18.04 查看本地镜像: docker images 运行容器 docker run -itd --name ubuntu-18-001 ubuntu:18.04 通过ps命令可以查看正在运行的容器信息 docker ps 进入容器 最…...

iOS问题记录 - App Store审核新政策:隐私清单 SDK签名(持续更新)
文章目录 前言开发环境问题描述问题分析1. 隐私清单 & SDK签名1.1. 隐私清单 - 数据使用声明1.2. 隐私清单 - 所用API原因描述1.3. SDK签名 2. 即将发布的第三方SDK要求 解决方案最后 前言 前段时间用Flutter开发的iOS App提交了新版本,结果刚过两分钟就收到了…...

ES学习日记(二)-------集群设置
上一节写了elasticsearch单节点安装和配置,现在说集群,简单地说就是在多台服务器上搭建单节点,在配置文件里面增加多个ip地址即可,过程同单节点部署,主要说集群配置 注意:不建议在之前单节点es上修改配置为集群,据说运行之后会生成很多文件,在单点基础上修改容易出现未知问题,…...

农村集中式生活污水分质处理及循环利用技术指南
立项单位:生态环境部土壤与农业农村生态环境监管技术中心、山东文远环保科技股份有限公司、北京易境创联环保有限公司、中国环境科学研究院、广东省环境科学研究院、中铁第五勘察设计院集团有限公司、中华环保联合会水环境治理专业委员会 本文件规定了集中式村镇生活…...

linux 一些命令
文章目录 linux 一些命令fdisk 磁盘分区parted 分区文件系统mkfs 格式化文件系统fsck 修复文件系统 mount 挂载swap 交换分区清除linux缓存df du 命令raid 命令基本原理硬raid 和 软raid案例raid 10 故障修复,重启与卸载 lvm逻辑卷技术LVM的使用方式LVM 常见名词解析…...

移动硬盘损坏打不开?别急,这里有解决方案!
在日常工作和生活中,移动硬盘几乎成为了我们必不可少的存储设备,它小巧便捷,能够容纳大量的数据。然而,当移动硬盘突然损坏打不开时,那份焦虑与无助几乎无法用言语来形容。那些重要的文件、珍贵的照片,似乎…...

微信小程序【从入门到精通】——服务器的数据交互
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...

Python爬虫-懂车帝城市销量榜单
前言 本文是该专栏的第23篇,后面会持续分享python爬虫干货知识,记得关注。 最近粉丝留言咨询某汽车平台的汽车销量榜单数据,本文笔者以懂车帝平台为例,采集对应的城市汽车销量榜单数据。 具体的详细思路以及代码实现逻辑,跟着笔者直接往下看正文详细内容。(附带完整代码…...

《QDebug 2024年3月》
一、Qt Widgets 问题交流 1. 二、Qt Quick 问题交流 1.Qt5 ApplicationWindow 不能使用父组件 Window 的 transientParent 属性 ApplicationWindow 使用 transientParent 报错: "ApplicationWindow.transientParent" is not available due to compone…...

C# OpenCvSharp-HoughCircles(霍夫圆检测) 简单计数
目录 效果 项目 代码 下载 效果 项目 代码 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; using OpenCvSharp; using O…...

MybatisPlus速成
MybatisPlus快速入门 快速入门入门案例常见注解常见配置 核心功能条件构造器自定义SQLService接口 扩展功能代码生成静态工具逻辑删除枚举处理器JSON处理器 插件功能分页插件通用分页实体 参考文档 mybatis-plus参考文档 全部资料链接 讲义 快速入门 入门案例 <dependency…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...