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

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...