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

算法进阶——链表中环的入口节点

题目


给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。

数据范围:1<=结点值<=10000

要求:空间复杂度O(1),时间复杂度O(n)

例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示:

可以看到环的入口结点的结点值为3,所以返回结点值为3的结点。

输入描述:

输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表。

返回值描述:

返回链表的环的入口结点即可,我们后台程序会打印这个结点对应的结点值;若没有,则返回对应编程语言的空结点即可。

示例1

输入:
{1,2},{3,4,5}
返回值:
3
说明:
返回环形链表入口结点,我们后台程序会打印该环形链表入口结点对应的结点值,即3 

示例2

输入:
{1},{}
返回值:
"null"
说明:
没有环,返回对应编程语言的空结点,后台程序会打印"null"

示例3

输入:
{},{2}
返回值:
2
说明:
环的部分只有一个结点,所以返回该环形链表入口结点,后台程序打印该结点对应的结点值,即2

思路


首先,题目中给的链表并不一定是有环的,所以需要先判断链表是否有环。可以在通过快慢指针的方式来判断,如果有环,则可以计算出环节点的个数。

然后,定义两个指针初始化指向头节点,第一个指针先前进环节点个数,之后两个节点同时前进,到节点值相等的节点就是环的入口节点。

本题还可以使用哈希表unordered_set来记录经过的节点来解决,但是这个方法的空间复杂度时O(n)。

另外,我的解法写的比较复杂,主要是为了理顺思路。使用快慢指针可以用更简洁的代码解决。

解答代码


/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {if (pHead == nullptr || pHead->next == nullptr) {return nullptr;}// 获取到环节点的个数int loop_node_num = GetLoopNodeNum(pHead);if (loop_node_num == 0) {// 链表中没有环return nullptr;}ListNode* pNode1 = pHead;ListNode* pNode2 = pHead;// 第一个节点先前进loop_node_num步for (int i = 0; i < loop_node_num; i++) {pNode1 = pNode1->next;}// 两个节点同时前进while (pNode1->val != pNode2->val) {pNode1 = pNode1->next;pNode2 = pNode2->next;}// 相等的点就是环的入口return pNode1;  }int GetLoopNodeNum(ListNode* pHead) {int loop_node_num = 0;// 定义快慢指针ListNode* fast = pHead->next;ListNode* slow = pHead;// 判断是否有环bool is_loop = false;while (fast != nullptr) {if (fast->val == slow->val) {is_loop = true;break;} else {if (fast->next != nullptr) {fast = fast->next->next;slow = slow->next;} else {break;}}}// 有环,则步进慢指针计算环的节点数if (is_loop) {int val = slow->val;loop_node_num = 1; // 加上自身while (val != slow->next->val) {++loop_node_num;slow = slow->next;}}return loop_node_num;}
};

相关文章:

算法进阶——链表中环的入口节点

题目 给一个长度为n链表&#xff0c;若其中包含环&#xff0c;请找出该链表的环的入口结点&#xff0c;否则&#xff0c;返回null。 数据范围&#xff1a;1<结点值<10000 要求&#xff1a;空间复杂度O(1)&#xff0c;时间复杂度O(n) 例如&#xff0c;输入{1,2},{3,4,5…...

无线WiFi安全渗透与攻防(N.1)WPA渗透-pyrit:batch-table加速attack_db模块加速_“attack_db”模块加速

WPA渗透-pyrit:batch-table加速attack_db模块加速_“attack_db”模块加速 WPA渗透-pyrit:batch-table加速attack_db模块加速_“attack_db”模块加速1.渗透WIFI1.导入密码字典2.导入essid,破解完成记得删除3.批处理数据库,速度比较慢,耐心等待4.batch-table(批处理数据库)加…...

YOLOV8部署Android Studio安卓平台NCNN

下载Android Studio&#xff0c;配置安卓开发环境&#xff0c;这个过程比较漫长。 安装cmake&#xff0c;注意安装的是cmake3.10版本。 根据手机安卓版本选择相应的安卓版本&#xff0c;我的是红米K30Pro&#xff0c;安卓12。 使用腾讯开源的ncnn&#xff0c;这是一个为手机端极…...

【算法萌新闯力扣】:旋转字符串

力扣热题&#xff1a;796.旋转字符串 开篇 今天下午刷了6道力扣算法题&#xff0c;选了一道有多种解法的题目与大家分享。 题目链接:796.旋转字符串 题目描述 代码思路 完全按照题目的要求&#xff0c;利用StringBuffer中的方法对字符串进行旋转&#xff0c;寻找相同的一项 …...

可逆矩阵的性质

如果矩阵A可逆&#xff0c;那么它的逆矩阵也可逆&#xff0c;并且如果矩阵A可逆&#xff0c;假设是一个不为0的数&#xff0c;那么也可逆&#xff0c;并且如果矩阵A和都可逆&#xff0c;而且它们的阶数也相同&#xff0c;那么它们的乘积也是可逆的&#xff0c;并且如果矩阵A可逆…...

HIT 模式识别 手写汉字分类 Python实现

训练集数据 TrainSamples-400.csv&#xff0c;含 100 个不同汉字&#xff0c;每个汉字 400 个实例&#xff0c;每个实例均为 64*64 的二值图像&#xff1b; 训练集标注TrainSamples-400.csv&#xff0c;为 40000 个 0 到 99 间的整数&#xff0c;表示训练集中每个实例所属汉字类…...

GPT-4V-Act :一个多模态AI助手,能够像人类一样模拟通过鼠标和键盘进行网页浏览。

内容来源&#xff1a;xiaohuggg GPT-4V-Act &#xff1a;一个多模态AI助手&#xff0c;能够像人类一样模拟通过鼠标和键盘进行网页浏览。 它可以模拟人类浏览网页时的行为&#xff0c;如点击链接、填写表单、滚动页面等。 它通过视觉理解技术识别网页上的元素&#xff0c;就像…...

剪辑视频怎么把说话声音转成文字?

短视频已然成为了一种生活潮流&#xff0c;我们每天都在浏览各种短视频&#xff0c;或者用视频的形式记录生活&#xff0c;在制作视频的时候&#xff0c;字幕是一个很大的问题&#xff0c;给视频添加字幕可以更直观、更方便浏览。手动添加太费时间&#xff0c;下面就给大家分享…...

maven打包插件配置模板

主要有两类&#xff1a; 1、maven-shade-plugin 主要用于java程序编写的的打包 <build><plugins><plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-shade-plugin</artifactId><version>3.2.4</ve…...

clusterProfiler包学习

&#x1f4d6; Introduction | Biomedical Knowledge Mining using GOSemSim and clusterProfiler (yulab-smu.top) 部分使用 #GO classificationlibrary(clusterProfiler) data(geneList, package"DOSE") gene <- names(geneList)[abs(geneList) > 2]# Entre…...

【Qt开发流程之】布局管理

介绍 一个界面呈现&#xff0c;如果要让用户有更好的观感&#xff0c;布局必不可少。 【Qt之布局】QVBoxLayout、QHBoxLayout、QGridLayout、QFormLayout介绍及使用 链接: https://blog.csdn.net/MrHHHHHH/article/details/133915208 qt布局类图&#xff1a; Qt布局是Qt图形…...

建筑可视化中的 3D 纹理

在线工具推荐&#xff1a; 三维数字孪生场景工具 - GLTF/GLB在线编辑器 - Three.js AI自动纹理化开发 - YOLO 虚幻合成数据生成器 - 3D模型在线转换 - 3D模型预览图生成服务 1、什么是 3D 纹理&#xff1f; 纹理是将二维图像添加到三维模型的技术艺术。虽然对物体进行纹…...

9.docker镜像Tag为none的原因

1.现象 使用docker images命令查看镜像列表&#xff0c;会发现存在许多标签为none的镜像&#xff1a; 2. 原因 docker镜像标签为none的原因如下&#xff1a; &#xff08;1&#xff09;构建或重新拉取同名同Tag的新镜像&#xff1a;构建或重新拉取同名同Tag的新镜像后&…...

HTML5学习系列之响应式图像

HTML5学习系列之响应式图像 前言响应式图像响应视图大小响应屏幕方向响应像素密度响应图像格式自适应像素比自适应视图宽 总结 前言 学习记录 响应式图像 响应视图大小 容器 srcset&#xff1a;图片地址&#xff0c;必需有。media&#xff1a;设置媒体查询。sizes&#xff…...

基于数据库(MySQL)与缓存(Redis)实现分布式锁

分布式锁 分布式锁&#xff1a;分布式锁是在分布式的情况下实现互斥类型的一种锁 实现分布式锁需要满足的五个条件 可见性&#xff1a;多个进程都能看到结果互斥性&#xff1a;只允许一个持有锁的对象的进入临界资源可用性&#xff1a;无论何时都要保证锁服务的可用性&#x…...

2023年A特种设备相关管理(锅炉压力容器压力管道)证模拟考试题库及A特种设备相关管理(锅炉压力容器压力管道)理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年A特种设备相关管理&#xff08;锅炉压力容器压力管道&#xff09;证模拟考试题库及A特种设备相关管理&#xff08;锅炉压力容器压力管道&#xff09;理论考试试题是由安全生产模拟考试一点通提供&#xff0c;A特…...

系统及其存储相关

1.区分系统&#xff08;软件&#xff09;和固件 1.1概念辨别 系统&#xff08;软件software&#xff09;&#xff1a; 角色&#xff1a; 系统是计算机中的核心软件&#xff0c;提供基本的管理、控制和资源分配功能。它通常包括操作系统&#xff0c;负责管理硬件资源、提供用户…...

鸿蒙原生应用开发-折叠屏、平板设备服务卡片适配

一、多设备卡片适配原则 为不同尺寸的卡片提供不同的功能 在卡片开发过程中请考虑适配不同尺寸的设备&#xff0c;特别是在折叠屏和平板设备上&#xff0c;设备屏幕尺寸的变化直接影响了卡片内容的展示。请发挥想象力设计具有自适应能力的卡片&#xff0c;避免在卡片内容不做…...

android查漏补缺(8)Android广播不同种类介绍

按照是否有序分类 1&#xff0c;普通广播&#xff08;无序广播&#xff09; 广播按照逻辑上同一时刻&#xff08;实际可能被CPU按照抢占式任务无序发给注册模块&#xff09;发送给注册模块 #发送方法&#xff1a; Context.sendBroadcast() 2&#xff0c;有序广播 广播按照…...

什么是美颜SDK?直播美颜SDK技术深度剖析

在实现实时美颜的过程中&#xff0c;美颜SDK扮演着关键的角色&#xff0c;它为开发者提供了一套强大的工具&#xff0c;使得实时美颜效果能够轻松应用于直播平台。 一、美颜SDK的基本概念 美颜SDK是一种软件工具包&#xff0c;通过集成了丰富的图像处理算法和实时计算技术&a…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...