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

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...