当前位置: 首页 > 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…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...