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

【数据结构】研究链表带环问题

💯💯💯💯

本篇主要研究的是链表带环问题,快慢指针的应用,分析不同解法对带环链表的处理,梳理完本篇你将对链表的理解更加透彻

  • Ⅰ.研究链表带环问题
  • Ⅱ.扩展带环问题
    • 1.为什么慢指针和快指针一定会相遇?
    • 2.快指针一次走3步,4步…n步可以吗?
    • 3.慢指针走的距离和快指针走的距离?
  • Ⅲ.总结归纳
    • 结论:带环定理
  • Ⅳ.带环链表真题
      • 方法1:利用带环定理
      • 方法2:转换为相交链表问题

Ⅰ.研究链表带环问题

链表带环是什么意思呢?
就是一个链表有一个结点指向了前面结点导致又链接回来的问题
如果进行遍历就会变成死循环
在这里插入图片描述

那么如何判断一个链表是否带环呢?
链表带环问题Ⅰ
在这里插入图片描述

思路:
我们可以利用快慢指针,慢指针走一步,快指针走两步,当快指针进入环中时,慢指针肯定还在外面,当慢指针进环时,快指针可能已经走了好几圈,但一旦两个指针进环后,肯定会相遇,我们可以将带环问题,转换为相遇问题,也就是小学经常看到的,小明先跑50,速度为5m/s,小亮后跑速度为10m/s,问何时相遇。

我们只要判断它们是否相遇了,就能确定是否带环,因为如果没有带环的话,那就不可能相遇,快指针肯定先走出去。

快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表其实位置开始运行,
如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。
在这里插入图片描述

bool hasCycle(struct ListNode *head){struct ListNode*fast,*slow;fast=slow=head;//快慢指针都从开头开始走while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow)//如果慢指针等于快指针则一定在环里return true;}return false;//否则就不在环里
}

Ⅱ.扩展带环问题

1.为什么慢指针和快指针一定会相遇?

假设链表带环,快慢指针同时走,快指针先入环,慢指针后入环,当慢指针刚入环时,有可能与快指针相遇,也有可能与快指针相差很远,但这不是问题,关键的关键是它们两都在环里,并且快指针每次走两步,慢指针每次走1步,而它们每次走一步时,它们之间的距离就减少1,每走一步,快指针就追上一步,所以它们之间的距离在不断的缩小,最后肯定能追上。
在这里插入图片描述

并且不会出现套圈的现象,因为两个结点之间最小的距离也就是1了,每次缩小1,最后要么重合,要么还是重合,不可能从头上跳过去的。

还有慢指针在慢指针走到一圈之前,快指针肯定是可以追得上慢指针的,即相遇
慢指针刚入环时,与快指针最远距离可能为一个环距离吧,但想一想,当慢指针走了一环距离时,快指针走了多少?快指针走的是慢指针的2倍呀,那肯定是2圈了都,慢指针走1圈,快指针都要走两圈了,这里面肯定追上慢指针了。

2.快指针一次走3步,4步…n步可以吗?

其实这种本质上看的是相对位移量,只要我们算出相对位移量就可以判断了。上面快指针每次走2步慢指针每次走1步,它们每次走一步都会缩小1距离,而因为1就是最小距离单位,所以最后肯定会相遇。
但如果一次走三步,就不一定了
假设快慢指针都入环后,它们之间的距离为N
快指针每次走3步,慢指针每次走1步,那它们每次走,快指针都会缩小2个距离,那它们之间的距离就变成了N-2,再走就变成N-4,N-6……,这里就涉及N是奇数还是偶数了,当N是偶数时,那么最后它们是可以相遇的,如果是奇数,那这圈是不会相遇的,不过最后走完快慢指针之间的距离就变成-1了,也就是这个环的周长减1距离,这又要取决于环的周长是偶数还是奇数了……。
在这里插入图片描述

如果快指针每次走4步,道理也是一样的,在快慢指针都入环后,假设它们的距离为N
则每次距离都会缩小3,则最好是否相遇取决于N是否是3的倍数了。
在这里插入图片描述

3.慢指针走的距离和快指针走的距离?

在这里插入图片描述

你想一想快指针和慢指针在相遇前总共走了多远距离呢?
快慢指针是同时从开始位置走的,快指针走的快,先入环,慢指针走的慢,后入环。
前面我们知道fast在slow走满一圈之前追上,所以slow不可能走过一圈的,所以慢指针走的总距离为L+M

而快指针就不一定了,快指针走的快,先入环,谁知道它在环里走了多少圈了都,而且走的圈数越多说明这个环越小
在这里插入图片描述
所以快指针走的总距离为
L+M+nC (n至少为1)*
n为走过的圈数

Ⅲ.总结归纳

因为快慢指针之间存在着关系,所以我们可以列出一个表达式,也就是快指针走的距离是慢指针走的距离的2倍
2*(L+M)=L+M+n*C

所以L=n*C-M
当最好情况下n=1时,L=C-M
L是什么?L就是开始点到入口点的距离
C-M是什么?C-M就是相遇点到入口点的距离。

也就是:一个指针从链表的起始位置开始运行,一个指针从相遇点位置绕环,每次都走一步,两个指针最终会在入口点的位置相遇

在这里插入图片描述

结论:带环定理

让一个指针从链表的起始位置开始遍历,同时让一个指针从带环的相遇点位置开始遍历,两个指针都是每次走一步,最终一定会在入环处相遇!

Ⅳ.带环链表真题

给定一个链表,返回链表开始入环的第一个结点,如果链表无环,则返回NULL
在这里插入图片描述
《链表带环问题Ⅱ》
要求判断是否有环,如果有请返回入环的第一个结点。

方法1:利用带环定理

这就是我上面两个例子的结合,第一步判断是否有环,第二步利用上面的定理:在有环的链表中,从开始位置和相遇点同时出发,将会在入环点相遇。

struct ListNode *detectCycle(struct ListNode *head) 
{//首先判断是否有环struct ListNode *fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){//fast与slow现在就是相遇点//这时从开始点和相遇点同时走,当相等时,就是入环点while(head!=slow)//如果不相同就一直走{head=head->next;slow=slow->next;}return head;//当跳出来时就是入环点}}return NULL;}

在这里插入图片描述

方法2:转换为相交链表问题

还有一种方法可以快速解决这个问题,我们可以将相遇点与后面那个结点断开
在这里插入图片描述
那从断开的结点开始是不是就相当于一个链表了,那这道题目就转变成了相交链表的问题了,求两个链表相交的结点问题,我在上一篇博客中有写过这种方法。
如果求两个相交链表的结点呢?
其实很简单:
第一步求出两个链表的长度
第二步让长度较长的链表先走长度差步
第三两个链表一起走,并进行比较,当两个链表的结点相同时就是相交结点。

在这里插入图片描述

struct ListNode *detectCycle(struct ListNode *head){//首先要找到相遇点,才能断开它struct ListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){//fast和slow现在就是相遇点,断开它和下一个结点并保存下一个结点的地址struct ListNode*newnode=slow->next;slow->next=NULL;//newnode就是新链表的头指针啦//开始求两个链表长度!int len1=0,len2=0;struct ListNode*tail1=head,*tail2=newnode;while(tail1)//计算链表1的长度{tail1=tail1->next;++len1;}while(tail2)//计算链表2的长度{tail2=tail2->next;++len2;}//两个链表长度是求出来来了,但不知道哪个是长链表哪个是短链表呀,所以还需要讨论下int gap=abs(len1-len2);struct ListNode*longlist=head,*shortlist=newnode;if(len1<len2){longlist=newnode;shortlist=head;}//让长的链表先走长度差while(gap--){longlist=longlist->next;}//然后两个链表再一起走,比较相同的时就是相交结点while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;//最后返回相交结点}}  return NULL;
}

在这里插入图片描述

相关文章:

【数据结构】研究链表带环问题

&#x1f4af;&#x1f4af;&#x1f4af;&#x1f4af; 本篇主要研究的是链表带环问题&#xff0c;快慢指针的应用&#xff0c;分析不同解法对带环链表的处理&#xff0c;梳理完本篇你将对链表的理解更加透彻Ⅰ.研究链表带环问题Ⅱ.扩展带环问题1.为什么慢指针和快指针一定会相…...

数据仓库的设计思想

数据仓库设计 知识点01&#xff1a;设计大纲与学习目标 #内容大纲1、数据仓库基础知识&#xff08;回顾&#xff09;什么是数仓为什么有数仓数仓的特点是什么OLTP和OLAP系统区别&#xff08;数据库和数仓的区别&#xff09;2、数仓系统的架构与核心流程核心1&#xff1a;ETL核…...

【JavaSE】数组的定义与使用详解

目录 1.数组的基本概念 1.1数组的好处 1.2什么是数组 1.3数组的定义及初始化 1.3.1数组的创建 1.3.2数组的初始化 1.4数组的使用 1.4.1访问数组中的元素 1.4.2遍历数组 2.数组的类型 2.1认识JVM的内存分布 2.2基本类型变量与引用类型变量 2.3认识null 3.数组的应…...

Kubernetes14:Helm为了部署像微服务这种的大型项目

Kubernetes14&#xff1a;Helm介绍&#xff08;为了部署像微服务这种的大型项目&#xff09; 1、Helm的引入 (1)之前方式部署应用基本过程 编写yaml文件 1、deployment kubectl create deployment nginx --imagenginx --dryrun -o yaml > nginx.yaml2、Service kubect…...

2.3操作系统-存储管理:页式存储、逻辑地址、物理地址、物理地址逻辑地址之间的地址关系、页面大小与页内地址长度的关系、缺页中断、内存淘汰规则

2.3操作系统-存储管理&#xff1a;页式存储、逻辑地址、物理地址、物理地址逻辑地址之间的地址关系、页面大小与页内地址长度的关系、缺页中断、内存淘汰规则页式存储逻辑地址、物理地址如何判断物理地址和逻辑地址它们之间的地址关系&#xff1f;页面大小与页内地址长度的关系…...

设计模式3——结构型模式

结构型模式描述如何将类或对象按某种布局组成更大的结构&#xff0c;它分为类结构型和对象结构型模式&#xff0c;前者采用继承机制来组织接口和类&#xff0c;后者采用组合或聚合来组合对象。 由于组合关系或聚合关系比继承关系耦合度低&#xff0c;满足“合成复用原则”&…...

css——图片缩放,拉伸,变形的解决办法

你的图片即将变得超级丝滑图片为什么会拉伸变形&#xff1f;怎么解决&#xff1f;css的object-fit属性object-fit属性有什么用介绍一下object-position举个小栗子图片为什么会拉伸变形&#xff1f; 前端布局时&#xff0c;图片会出现拉伸、缩放和变形的原因可能有多种: 1.例如图…...

【工具使用】STM32CubeMX-基础使用篇

一、概述 无论是新手还是大佬&#xff0c;基于STM32单片机的开发&#xff0c;使用STM32CubeMX都是可以极大提升开发效率的&#xff0c;并且其界面化的开发&#xff0c;也大大降低了新手对STM32单片机的开发门槛。     本文主要面向初次接触STM32CubeMX的同学&#xff0c;大…...

面试题解-理解cookie、session和token

项目vuespringboot 1、token 用户填写密码账号发送至后端&#xff0c;由后端生成token&#xff0c;返回给前端&#xff0c;前端把它存放起来&#xff0c;如放在cookie或者localStorage里面 前端向服务器发起请求时在请求头携带token&#xff0c;判断用户身份给与反应。 //后…...

Buuctf [GUET-CTF2019]number_game 题解

目录 一.主函数逻辑 二.level_stor()函数 三.mid_stor函数 四.operate函数 五.judge2函数 六.求解flag 一.主函数逻辑 ①先输入一个字符串,然后judge1()函数遍历它,判断字符是否在[0,4]区间范围内 ②将输入的字符串用层次遍历的方式存储为一个二叉树root ③再将二叉树r…...

OsgEarth配置.earth文件支持wms服务

<!-- 参考 http://vmap0.tiles.osgeo.org/wms/vmap0?LAYERSbasic&SERVICEWMS&VERSION1.1.1&REQUESTGetMap&STYLES&FORMATimage%2Fjpeg&SRSEPSG%3A4326&BBOX-90,45,-45,90&WIDTH256&HEIGHT256 --> <!-- 可用 2023.03.09--> …...

【数据结构】详解空间复杂度

Yan英杰的博客 悟已往之不谏 知来者之可追 目录 空间复杂度 ​案例1:计算BubbleSort的空间复杂度&#xff1f; 案例2:计算斐波那契额数列的前N项的空间复杂度 案例3:计算阶乘递归Fac的空间复杂度&#xff1f; 案例4:F1和F2两函数是否使用的同一块空间 案例5:计算该…...

腾讯云GPU游戏服务器/云主机租用配置价格表

用于游戏业务的服务器和普通云服务器和主机空间是不同的&#xff0c;游戏服务器对于硬件的配置、网络带宽有更大的要求&#xff0c;一般游戏服务器根据不同的配置和适用场景会有十几元一小时到几十元一小时&#xff0c;而且可以根据不同的按量计费。而普通的云服务器可能需要几…...

配置临时SSL子域名泛化证书

配置临时SSL子域名泛化证书 三个月有效期第一步&#xff1a;访问SSL证书地址第二步&#xff1a;在华为云上/其他服务器上搜索DNS云解析服务类似的功能第三步&#xff1a;将SSL申请的信息添加到服务器的记录集中第四步&#xff1a;添加完信息进行保存获取key / crt第五步&#x…...

【Linux:环境变量的理解】

目录 1 Z(zombie)-僵尸进程 2 孤儿进程 3 环境变量 3.1 基本概念 3.2 测试HOME 3.3 和环境变量相关的命令 3.4 环境变量的组织方式 3.5 环境变量通常是具有全局属性的 在讲环境变量之前&#xff0c;我们先把上次遗留知识点给总结了&#xff08;僵尸进程和孤儿进程&…...

python数据类型与数据结构

目录 一、数据类型 1.1变量与常量 1.1.1变量 1.1.2常量 1.2字符串类型 1.3整数与浮点数 1.4List列表 1.5 元组tuple 1.6字典dict 二、字符串格式化 三、数据输入和类型转换 四、简单列表习题练习 一、数据类型 变量类型&#xff1a; 整数int&#xff08;4字节&#x…...

大数据自学学习技巧?

经常有人说&#xff1a;先别管大数据是什么&#xff0c;现在理解不了没关系&#xff0c;先开始学&#xff0c;等学着学着就明白了&#xff0c;这种学习路线基本是混合的&#xff0c;很难分清楚自己学了这段怎么用在以后项目中&#xff0c;所以会越学越迷茫&#xff0c;但是等你…...

Qt音视频开发22-音频播放QAudioOutput

一、前言 以前一直以为只有Qt5以后才有QAudioOutput播放音频&#xff0c;其实从Qt4.6开始就有&#xff0c;在Qt6中变成了QAudioSink&#xff0c;功能一样。用QAudioOutput播放音频pcm数据极其方便&#xff0c;只需要指定音频播放设备&#xff08;可能电脑上有多个音频输出设备…...

JavaEE简单示例——Spring的入门程序

简单介绍&#xff1a; 在之前我们简单的介绍了有关于Spring的基础知识&#xff0c;那么现在我们就来一步步的把理论融入到实践中&#xff0c;开始使用这个框架&#xff0c;使用过程也是非常的简单&#xff0c;大致可以分为几个基础的步骤&#xff1a; 1.首先引入Spring的Mave…...

【嵌入式Bluetooth应用开发笔记】第一篇:DBUS概述与蓝牙开发小试牛刀

DBUS概述 DBus&#xff08;D-Bus&#xff09;是一个在不同程序之间传递消息的系统总线。DBus为不同的程序之间提供了一种通信机制&#xff0c;这种通信制可以在不需要知道对方程序的情况下进行通信。 DBus可以使用多种编程语言来开发&#xff0c;包括C、C、Python、Java等。在…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

UDP(Echoserver)

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

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...