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

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 + x
C + 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 + x
C +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实现选项框内容过长&#xff0c;截取显示功能&#xff1a; <el-select popper-class"popper-class" :popper-append-to-body"false" v-model"value" placeholder"请选择"><el-optionv-for"item in opt…...

K8S面试题学习5

参考K8S面试题&#xff08;史上最全 持续更新&#xff09;_kubernetes常见面试题-CSDN博客做的个人总结&#xff0c;规划是每天看10题&#xff0c;thx&#xff01; 1. 请详述kube-proxy原理? 每个node节点都会运行一个kube-proxy的进程&#xff0c;核心功能是将service的访问…...

字符以及字符串函数

字符以及字符串函数 求字符串长度strlen 长度不受限制的字符串函数strcpystrcatstrcmp 长度受限制的字符串函数strncpystrncatstrncmp 字符串查找strstrstrtok 错误信息报告strerror 字符分类函数字符转换函数tolowertoupper 内存操作函数memcpymemmovememcmpmemset 这篇文章注…...

记录解决问题--redis ssl连接

1.问题场景 springboot连接redis启动报错&#xff0c;感觉是没连上redis&#xff0c;本地是正常启动的&#xff0c;但是本地不是ssl连接。 2.redis ssl连接知识 ①一般不开启ssl的连接&#xff0c;直接连接即可&#xff0c;有密码输密码。 ②不受信的ssl连接&#xff0c;也就…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; 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的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Opencv中的addweighted函数

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

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

c#开发AI模型对话

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

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...