每日一题(相交链表 )
欢迎大家来我们主页进行指导
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…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...

若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...

PLC入门【4】基本指令2(SET RST)
04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C),从 文件 - 主画面,“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...

篇章一 论坛系统——前置知识
目录 1.软件开发 1.1 软件的生命周期 1.2 面向对象 1.3 CS、BS架构 1.CS架构编辑 2.BS架构 1.4 软件需求 1.需求分类 2.需求获取 1.5 需求分析 1. 工作内容 1.6 面向对象分析 1.OOA的任务 2.统一建模语言UML 3. 用例模型 3.1 用例图的元素 3.2 建立用例模型 …...
Java严格模式withResolverStyle解析日期错误及解决方案
在Java中使用DateTimeFormatter并启用严格模式(ResolverStyle.STRICT)时,解析日期字符串"2025-06-01"报错的根本原因是:模式字符串中的年份格式yyyy被解释为YearOfEra(纪元年份),而非…...