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

【题解】判断链表中是否有环、链表中环的入口结点

文章目录

  • 判断链表中是否有环
  • 链表中环的入口结点

判断链表中是否有环

题目链接:判断链表中是否有环

解题思路1:快慢指针

代码如下:

    bool hasCycle(ListNode *head) {if(head == nullptr) return false;ListNode* fast = head;ListNode* slow = head;while(fast!=nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow){return true;}}return false;}

解题思路2:hash法

我们把所有的节点放到哈希表中,我们遍历整个链表,如果存在重复的相同节点,那就证明链表中有环

代码如下:

    bool hasCycle(ListNode *head) {map<ListNode*, int> mp;ListNode* cur = head;while(cur != nullptr){if(mp[cur] == 1) return true;mp[cur] = 1;cur = cur->next;}return false;}

链表中环的入口结点

题目链接:链表中环的入口结点

解题思路1:hash法,记录第一次重复的节点

代码如下:

    ListNode* EntryNodeOfLoop(ListNode* pHead) {map<ListNode*, int> mp;ListNode* cur = pHead;while (cur != nullptr) {if (mp[cur] == 1) return cur;mp[cur] = 1;cur = cur->next;}return nullptr;}

解题思路2:快慢指针

上面我们用快慢指针来判断一个链表是否有环,我们也可以通过快慢指针来找到环的入口节点。我们要找到快慢指针之间步数的数学关系,借助数学关系来找到环的入口节点
假设从头结点到环的入口节点一共有a个节点,环中的节点一共有b个,设快指针走的步数为f,慢指针走的步数为s,那么有步数之间有这样的数学关系:

  • f = 2 * s ;快指针一次走两步,慢指针一次走一步
  • f = s + nb ;当快慢指针相遇时,快指针一定比慢指针多走了nb步,意思就是多绕环了n圈

所以可以得出:s = nb,f = 2nb;

当快慢指针相遇时,慢指针已经走了nb步,快指针走了2nb步,同时我们要走到环的入口节点需要走a + kb 步,而这时慢指针的nb只要再走a步即可到达入口,所以我们把快指针移动到头节点,之后,再让两个指针一次走一步往前走,当他们相遇时所处的节点就是入口节点

代码如下:

    ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* fast = pHead;ListNode* slow = pHead;while(fast != nullptr){slow = slow->next;if(fast->next == nullptr) return nullptr;//链表中无环fast = fast->next->next;if(fast == slow){//快慢指针相遇fast = pHead;//让快指针重新指向pHeadwhile(fast != slow){//通过两个指针的相遇,控制fast走a步fast = fast->next;slow = slow->next;}return fast;//此时fast即是入口节点,直接返回}}return nullptr;}

相关文章:

【题解】判断链表中是否有环、链表中环的入口结点

文章目录 判断链表中是否有环链表中环的入口结点 判断链表中是否有环 题目链接&#xff1a;判断链表中是否有环 解题思路1&#xff1a;快慢指针 代码如下&#xff1a; bool hasCycle(ListNode *head) {if(head nullptr) return false;ListNode* fast head;ListNode* slow …...

Pytorch 最全入门介绍,Pytorch入门看这一篇就够了

本文通过详细且实践性的方式介绍了 PyTorch 的使用&#xff0c;包括环境安装、基础知识、张量操作、自动求导机制、神经网络创建、数据处理、模型训练、测试以及模型的保存和加载。 1. Pytorch简介 在这一部分&#xff0c;我们将会对Pytorch做一个简单的介绍&#xff0c;包括它…...

Lambda 表达式的作用域

在Lambda表达式中访问外层作用域和旧版本的匿名对象中的方式类似。你可以直接访问标记了final的外层局部变量&#xff0c;或者实例的字段以及静态变量。 Lambda表达式不会从超类&#xff08;supertype&#xff09;中继承任何变量名&#xff0c;也不会引入一个新的作用域。Lambd…...

【portswigger】第二专题-XSS(二)

portswigger 靶场&#xff08;第二章节&#xff09;XSS 视频同步更新至bilibili bibi地址 【【portswigger】第二专题-XSS&#xff08;一前置知识&#xff09;】 https://www.bilibili.com/video/BV1mp4y157xA/?share_sourcecopy_web 【【portswigger】第二专题-XSS&#xff…...

【计算机视觉|人脸建模】3D人脸重建基础知识(入门)

本系列博文为深度学习/计算机视觉论文笔记&#xff0c;转载请注明出处 一、三维重建基础 三维重建&#xff08;3D Reconstruction&#xff09;是指根据单视图或者多视图的图像重建三维信息的过程。 1. 常见三维重建技术 人工几何模型仪器采集基于图像的建模描述基于几何建模…...

使用Jetpack Glance创建Android Widget

使用Jetpack Glance创建Android Widget Jetpack Glance发布&#xff0c;让我们使用Google提供的Jetpack Glance创建一个联系人列表小部件。 https://developer.android.com/jetpack/compose/glance 什么是Glance&#xff1f; Jetpack Glance是一个使用Kotlin API创建小型、轻…...

【MyBatis 学习三】子段不一致问题 多表查询 动态SQL

目录 一、解决Java实体类属性与数据库表字段不一致问题 &#x1f337;现象1&#xff1a;显示字段不对应&#xff1a;使用ResultType查询结果为null&#xff1b; &#x1f337;解决办法&#xff1a;字段不对应&#xff1a;使用ResultMap解决。 二、数据库的多表查询 &#…...

15. Spring AOP 的实现原理 代理模式

目录 1. 代理模式 2. 静态代理 3. 动态代理 3.1 JDK 动态代理 3.2 CGLIB 动态代理 4. JDK 动态代理和 CGLIB 动态代理对比 5. Spring代理选择 6. Spring AOP 实现原理 6.1 织入 7. JDK 动态代理实现 8. CGLIB 动态代理实现 9. 总结 1. 代理模式 代理模式&#xf…...

死锁产生的原因以及解决方案

一.原因: 1.使用互斥锁. 2.除非主动释放,负责不能被抢占. 3.占用一把锁不释放,等待其它锁资源(保持现状). 4.锁形成环路. 二.解决方案: 给锁编号,上锁的时候从小到大依次上锁,譬如如果一个线程要上1号和2号两把锁,如果1号锁被占用,不能上2号锁,等其它线程释放1号锁资源后…...

【构造】CF1758 D

Problem - D - Codeforces 题意&#xff1a; 思路&#xff1a; 如果需要构造一个和为定值的序列&#xff0c;那么考虑n-d,n-d1,.....nd-1,nd这种形式 如果要保证不能重复&#xff0c;那么先考虑一个排列&#xff0c;然后在排列上操作 如果根据小数据构造出了一些简单情形&a…...

【腾讯云 Cloud Studio 实战训练营】永不宕机的IDE,Coding Everywhere

【腾讯云 Cloud Studio 实战训练营】永不宕机的IDE&#xff0c;随时随地写代码&#xff01; 写在最前视频讲解&#xff1a;Cloud Studio活动简介何为腾讯云 Cloud Studio?Cloud Studio简介免费试用&#xff0c;上手无忧Cloud Studio 特点及优势云端开发多种预制环境可选metawo…...

JavaScript将一层级对象数组转为children嵌套的三层级树状对象数组(多级树状分类)

有时候后端返回的数据不适合前端,我们就需要进行转换,比如我想用elementUI的级联选择器,而这个组件对数据格式有要求,本篇文章将介绍如何将一层级对象数组数据格式转为三层级嵌套children数组,JavaScript、Vue、小程序等都适用,使用情景为多级分类,嵌套数据 情况1:原数…...

Windows脚本启动Redis、Java和Nginx服务指南

文章目录 1. 完整的批处理脚本2. Redis服务3. Java服务4. Nginx服务 1. 完整的批处理脚本 echo offcd C:\path\to\redis tasklist /FI "IMAGENAME eq redis-server.exe" 2>NUL | find /I /N "redis-server.exe">NUL if "%ERRORLEVEL%"&qu…...

【宝藏系列】STM32之C语言基础知识

【宝藏系列】STM32之C语言基础知识 文章目录 【宝藏系列】STM32之C语言基础知识1️⃣位操作2️⃣define宏定义3️⃣ifdef条件编译4️⃣extern变量声明5️⃣typedef类型别名 C语言是单片机开发中的必备基础知识&#xff0c;本文列举了部分 STM32 学习中比较常见的一些C语言基础知…...

探索自除数:发现区间内的神奇数字

本篇博客会讲解力扣“728. 自除数”的解题思路&#xff0c;这是题目链接。 对于给定的正整数num&#xff0c;我们如何判断它是不是自除数呢&#xff1f;根据定义&#xff0c;我们只需要把num的每一位数字都取出来&#xff0c;判断能不能整除num&#xff0c;如果发现num的某一位…...

打卡力扣题目四

#左耳听风 ARST 打卡活动重启# 目录 一、题目 二、解题代码 三、解题思路 关于 ARTS 的释义 —— 每周完成一个 ARTS&#xff1a; ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享…...

npm yarn nrm

npm 和 yarn npm和yarn都是包管理器&#xff0c;yarn是在2016年发布的&#xff0c;那时npm还处于V3时期&#xff0c;那时候还没有package-lock.json文件&#xff0c;不稳定性、安装速度慢等缺点经常会受到广大开发者吐槽。此时&#xff0c;yarn 诞生了。yarn 的优点&#xff0c…...

关于我对刚开始学Java的小白想分享的内容:

编程是很有魅力的&#xff0c;让很多人为之痴迷 如果你是初学者&#xff0c;俗称小白&#xff0c;不妨看看下述内容&#xff1a; 文章目录 1. Java 简介 Java 是一门编程语言&#xff0c;发展至今已经成为一门真正意义上的语言标准。 Java是一个完整的平台&#xff0c;有一个…...

Redis学习路线(5)—— Redis生成唯一ID

一、全局唯一ID &#xff08;一&#xff09;在用户抢购时&#xff0c;就会生成订单并保存到数据库中&#xff0c;而订单表如果使用自增ID就会存在以下几种情况&#xff1a; 自增ID规律性太强受单表数据量的限制 &#xff08;二&#xff09;全局ID生成器&#xff0c;是一种在…...

django后台系统Tyadmin

无意之间发现个django的后台管理框架&#xff0c;仔细与xadmin对比了一下&#xff0c;无论是功能上还是便携性上都与xadmin特别相似&#xff0c;但个人感觉Tyadmin略胜一筹&#xff0c;因为外观上要比xadmin要美观&#xff0c;而且相比起来速度也快&#xff0c;部署甚至也和简单…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...