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

ESP32读取DHT11温湿度数据

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

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

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

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* 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

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

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势

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

PLC入门【4】基本指令2(SET RST)

04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)&#xff0c;从 文件 - 主画面&#xff0c;“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并启用严格模式&#xff08;ResolverStyle.STRICT&#xff09;时&#xff0c;解析日期字符串"2025-06-01"报错的根本原因是&#xff1a;模式字符串中的年份格式yyyy被解释为YearOfEra&#xff08;纪元年份&#xff09;&#xff0c;而非…...