C语言 [力扣]详解环形链表和环形链表II
各位友友们,好久不见呀!又到了我们相遇的时候,每次相遇都是一种缘分。但我更加希望我的文章可以帮助到大家。下面就来具体看看今天所要讲的题目。
文章目录
- 1.环形链表
- 2.环形链表II
1.环形链表
题目描述:https://leetcode.cn/problems/linked-list-cycle/description/
这道题目呢,现阶段使用C语言的最优方案就是使用快慢指针的方法。下面就让我给大家介绍如何使用快慢指针的方法来解决这道题目。
我们假设让快指针一次走两步,慢指针一次走一步。下面我将用图来更直观描述此题的逻辑。
1.当fast指针准备进环时,slow指针才走了fast指针的一半。
2.当slow指针准备进环时,fast指针已经在环内转了几圈了。
3.当slow指针进环时,fast指针就开始追击slow指针
走到这里,这道题目实际上就变成了追击问题。当fast指针追上slow指针时,说明该链表是带环链表。反之则为不带环链表。
思路清晰,下面请看代码实现:
bool hasCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast -> next){fast = fast -> next ->next;slow = slow ->next;if(slow == fast){return true;}}return false;
}
其实,这道题目还有两个问题:
1:为什么两个指针一定会相遇?有没有可能会错过,或者永远追不上?
2:当slow走一步时,可不可以让fast指针一次走3步或者其它的步数呢?
下面就根据以上两个问题分别讨论一下
1.我们假设slow进环时,slow跟fast的距离为N
当fast开始追击slow的时候,它们之间的距离变成N-1、N-2…直到0。说明它们每追击一次,它们之间的距离就缩小1,而距离为0时则它们相遇。
2.我们假设分析一下slow指针一次走一步,fast指针一步走三步的情况
1)当slow走了三分之一时,fast指针已经准备开始进环了。
2.当slow指针走了三分之二时,fast指针已经在环内转了几圈了。
3.当slow指针准备进环时,fast指针又在环内转了不知道多少圈
我们还是假设slow指针进环时,fast指针和slow指针的距离为N
当fast指针开始追击slow指针时,它们的距离变化为:N-2、N-4、…
到这里,就有两种情况产生:
①当N为偶数时:则最终的距离会变成0,则说明他们相遇
②当N为奇数时:则最终的距离会变成-1,则说明它们错过了,进入新一轮的追击。
我们假设C代表环的长度,那么新一轮追击的距离就变成C-1了。
这里又有两种情况:
1)当C-1为偶数时:则来到第①这种情况,最后会追上。
2)当C-1为奇数时:则来到第②这种情况,它们将永远错过,无法相遇,陷入死循环。
那么当C为偶数,N为奇数时,则说明它们无法相遇,是否会有这种情况发生呢?
我们假设当slow指针准备进入环时,slow指针走过的距离为L,fast指针走过的距离为L + xC + C-N。因此,我们会产生一条等式:
3L = L + xC + C - N 化简就变为: 2L = (x+1)*C - N
偶数 = (x+1) × 偶数 - 奇数 ? 这显然等式不成立,则说明不可能存在C为偶数,N为奇数的这种情况,即不存在追不上的这种情况。
讨论完fast指针走三步的情况,那么fast指针走n步的情况也跟以上的方法类似,只不讨论的过程会更加繁琐一点。
2.环形链表II
题目描述:https://leetcode.cn/problems/linked-list-cycle-ii/description/
这一道题目的解法也是用快慢指针这一方法。
想要找到入口点,最简单的办法就是让一个指针从头开始走,一个指针从fast指针和slow指针相遇的位置开始走,当两个指针相遇时,则找到入口点。
代码展示:
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast = head,*slow = head;while(fast && fast->next){fast = fast -> next -> next;slow = slow -> next;//如果相遇了if(slow == fast){struct ListNode* meet = slow;while(meet != head){meet = meet -> next;head = head -> next;}return meet;}}return NULL;
}
现在又有一个问题:为什么入口点就在那个地方呢?下面就对其进行证明:
假设从头开始走到入口点的距离为L,slow进环走的距离为N,环形链表的长度为C
那么当fast指针和slow指针相遇时:
fast指针走过的路程为: L + xC +N (x>=1的整数)
slow指针走过的路程为: L + N
因此我们得到一条等式: 2(L + N) = L + xC +N (x>=1)
化简得: L = x*C - N,便于观察,我们可以将等式变为 L = (x-1)*C + C - N
因此,不管x的值为多少,只需让相遇点多走C - N的距离,就能说明head指针和meet指针相遇,从而找到入口点。
今天的分享就到这里啦,如果感觉内容不错,记得一键三连噢。创作不易,感谢大家的支持,我们下次再见!ヾ( ̄▽ ̄)ByeBye
相关文章:

C语言 [力扣]详解环形链表和环形链表II
各位友友们,好久不见呀!又到了我们相遇的时候,每次相遇都是一种缘分。但我更加希望我的文章可以帮助到大家。下面就来具体看看今天所要讲的题目。 文章目录 1.环形链表2.环形链表II 1.环形链表 题目描述:https://leetcode.cn/problems/link…...

Threejs 学习笔记 | 灯光与阴影
文章目录 Threejs 学习笔记 | 灯光与阴影如何让灯光照射在物体上有阴影LightShadow - 阴影类的基类平行光的shadow计算投影属性 - DirectionalLightShadow类平行光的投射相机 聚光灯的shadow计算投影属性- SpotLightShadow类聚光灯的投射相机 平行光 DirectionalLight聚光灯 Sp…...
SSH:安全远程访问的基石
SSH:安全远程访问的基石 一、引言 在当今这个数字化、网络化的时代,远程访问和管理计算机资源已成为日常工作的重要组成部分。然而,如何在不安全的网络环境中确保数据传输的机密性、完整性和可靠性,成为了一个亟待解决的问题。S…...

杰发科技AC7801——ADC之Bandgap和内部温度计算
0. 参考 电流模架构Bandgap设计与仿真 bandgap的理解(内部带隙电压基准) 虽然看不懂这些公式,但是比较重要的一句应该是这个:因为传统带隙基准的输出值为1.2V 1. 使用 参考示例代码。 40002000是falsh控制器寄…...
了解 macOS 中的系统完整性保护 (SIP):开启与关闭
在 macOS 系统中,有一个名为系统完整性保护 (System Integrity Protection,SIP) 的重要功能。SIP 旨在保护系统文件和进程免受未经授权的访问和修改,从而提高系统的安全性和稳定性。然而,在某些情况下,用户可能需要临时…...

【Linux】简易进度条的实现
🎉博主首页: 有趣的中国人 🎉专栏首页: Linux 🎉其它专栏: C初阶 | C进阶 | 初阶数据结构 小伙伴们大家好,本片文章将会讲解Linux中进度条的实现的相关内容。 如果看到最后您觉得这篇文章写得…...

Docker + Django跨域解决方案
什么是Django Django 是一个开源的高级 Python Web 框架,它鼓励快速开发并遵循可重用和可维护的实践。Django 是在 MTV(模型-模板-视图)模式的基础上设计的,这个模式类似于但不同于 MVC(模型-视图-控制器)模…...

Maven 插件使用
1.spring-boot-maven-plugin 我们直接使用 maven package (maven自带的package打包功能),打包Jar包的时候,不会将该项目所依赖的Jar包一起打进去,在使用java -jar命令启动项目时会报错,项目无法正常启动。…...

【HMGD】GD32/STM32 DMA接收不定长串口数据
单片机型号:GD32F303系列 CubeMX配置 配置串口参数 开启DMA 开启中断 示例代码 使用到的变量 uint8_t RX_Buff_FLAG 0; uint8_t RX_Buff[300] {0}; uint8_t TX_Buff[300] {0};串口接收空闲函数 // 串口接收空闲函数 void HAL_UARTEx_RxEventCallback(UART_H…...

局域网手机端远程控制手机
局域网手机端远程控制手机 随着科技的进步和智能设备的普及,远程控制技术在日常生活与工作中的应用越来越广泛。其中,局域网内的手机端远程控制手机技术,因其便捷性和实用性,受到了众多用户的关注。本文将简要介绍该技术及其应用…...
如何在OpenWrt软路由中增加一个新功能
为了在OpenWrt中增加一个新的功能,并使其支持 UCI 配置,我们可以创建一个简单的C语言服务,例如一个简单的日志服务。此服务将记录到日志文件中,并支持通过 UCI 配置启用或禁用日志功能。以下是详细的步骤和代码示例。 1 创建服务…...

【linux】vmtouch文件缓存管理工具
目录 vmtouch简介 用法 例子 统计文件或者目录在缓存中的记录 缓存文件到内存 其他类似工具 vmtouch简介 vmtouch是用c语言编写的文件缓存管理工具,适用用于所有类Unix系统。 作用: 1,查看文件系统缓存情况 2,将文件或目…...

论文阅读:The Unreasonable Ineffectiveness of the Deeper Layers 层剪枝与模型嫁接的“双生花”
作者实证研究了针对流行的开放式预训练 LLM 系列的简单层修剪策略,发现在不同的 QA 基准上,直到去掉一大部分(最多一半)层(Transformer 架构)后,性能的下降才会降到最低。为了修剪这些模型&…...

Python批量备份华为设备配置到FTP服务器
Excel表格存放交换机信息: 备份文件夹效果图: Windows系统配置计划任务定时执行python脚本: Program/script:C:\Python\python.exe Add arguments (optional): D:\Python_PycharmProjects\JunLan_pythonProje…...
Java虚拟机(JVM)中确保资源及时释放的策略
在Java虚拟机(JVM)中,内存管理主要是通过垃圾回收(Garbage Collection, GC)来自动处理的。Java开发者通常不需要(也不应该)显式地释放对象内存,因为JVM的垃圾回收器会自动处理不再使…...

04-Fortran基础--Fortran数组和矩阵运算
04-Fortran基础--Fortran数组和矩阵运算 fortarn中对数组和矩阵的主要操作和内置运算包括: 数组的声明和初始化:fortarn中可以通过声明和初始化来创建数组。例如: integer :: my_array(3) [1, 2, 3] ! 声明一个包含3个整数的数组并初始化数…...

el-select选项框内容过长
利用popper-class实现选项框内容过长,截取显示功能: <el-select popper-class"popper-class" :popper-append-to-body"false" v-model"value" placeholder"请选择"><el-optionv-for"item in opt…...
K8S面试题学习5
参考K8S面试题(史上最全 持续更新)_kubernetes常见面试题-CSDN博客做的个人总结,规划是每天看10题,thx! 1. 请详述kube-proxy原理? 每个node节点都会运行一个kube-proxy的进程,核心功能是将service的访问…...

字符以及字符串函数
字符以及字符串函数 求字符串长度strlen 长度不受限制的字符串函数strcpystrcatstrcmp 长度受限制的字符串函数strncpystrncatstrncmp 字符串查找strstrstrtok 错误信息报告strerror 字符分类函数字符转换函数tolowertoupper 内存操作函数memcpymemmovememcmpmemset 这篇文章注…...
记录解决问题--redis ssl连接
1.问题场景 springboot连接redis启动报错,感觉是没连上redis,本地是正常启动的,但是本地不是ssl连接。 2.redis ssl连接知识 ①一般不开启ssl的连接,直接连接即可,有密码输密码。 ②不受信的ssl连接,也就…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...