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

每日一题(相交链表 )

欢迎大家来我们主页进行指导
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. 相交链表 - 力扣&#xff08;LeetCode&#xff09; 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节…...

C#WPF控件大全

本文列出WPF控件大全,点击可以进入详情页查看。 列表如下: AccessText用下划线来指定用作访问键的字符。 ActivatingKeyTipEventArgs为 ActivatingKeyTip 事件提供数据。...

好书推荐 《AIGC重塑金融》

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

【Linux】权限理解

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

插入排序、归并排序、堆排序和快速排序的稳定性分析

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

【pytest、playwright】多账号同时操作

目录 方案实现思路&#xff1a; 方案一&#xff1a; 方案二&#xff1a; 方案实现思路&#xff1a; 依照上图所见&#xff0c;就知道&#xff0c;一个账号是pytest-playwright默认的环境&#xff0c;一个是 账号登录的环境 方案一&#xff1a; 直接上代码&#xff1a; imp…...

软考 系统架构设计师系列知识点之云原生架构设计理论与实践(8)

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

【C++】stack、queue和优先级队列

一、前言 二、stack类 2.1 了解stack 2.2 使用stack &#xff08;1&#xff09;empty &#xff08;2&#xff09;size &#xff08;3&#xff09;top &#xff08;4&#xff09;push &#xff08;5&#xff09;pop 2.3 stack的模拟实现 三、queue类 3.1 了解queue …...

第十三届蓝桥杯国赛真题 Java C 组【原卷】

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

docker部署ubuntu

仓库&#xff1a; https://hub.docker.com/search?qUbuntu 拉一个Ubuntu镜像 docker pull ubuntu:18.04 查看本地镜像&#xff1a; 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提交了新版本&#xff0c;结果刚过两分钟就收到了…...

ES学习日记(二)-------集群设置

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

农村集中式生活污水分质处理及循环利用技术指南

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

linux 一些命令

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

移动硬盘损坏打不开?别急,这里有解决方案!

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

微信小程序【从入门到精通】——服务器的数据交互

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

Python爬虫-懂车帝城市销量榜单

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

《QDebug 2024年3月》

一、Qt Widgets 问题交流 1. 二、Qt Quick 问题交流 1.Qt5 ApplicationWindow 不能使用父组件 Window 的 transientParent 属性 ApplicationWindow 使用 transientParent 报错&#xff1a; "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 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Unity3D中Gfx.WaitForPresent优化方案

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

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; 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&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

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

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...