【证明】快慢指针在带环链表中是否存在无法相遇的情形

2024-04-30 22:04

本文主要是介绍【证明】快慢指针在带环链表中是否存在无法相遇的情形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P. S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。
P. S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。

  

目录

  • 1. 前言
  • 2. 证明过程
    • 2.1 证明
    • 2.2 加证
  • 3. 结论
  • 4. 结语

1. 前言


  在了解本次内容前,可以先了解一下带环链表中使用快慢指针来判断链表是否带环的内容。

  链表带环问题之判断链表是否带环

在这里插入图片描述
  而本文我们探究的问题是快慢指针在带环链表中是否存在无法相遇的情形,在此背景下,我们的快慢指针之间的速度比可以不再是快指针走两步,慢指针走一步,而是可以将他们定位任意的步数,只要快指针走的比慢指针快即可。

  本问探究的情况是当快指针依次走三步,慢指针一次走一步的情形,此情形的道德结论同样适用于其他速率比(例如 3:5,2:5)。

  PS.下述证明过程中的速率比均为实际步数比,
  例如 3:1为FAST走三步,SLOW走一步。
  例如 4:3为FAST走四步,SLOW走三步。



2. 证明过程

2.1 证明


  
FASTSLOW
31

在这里插入图片描述
  在此处我们直接快进到SLOW到达入环点的时刻,此时FAST想要追到SLOW还需要追赶的距离为N。
  在上文中我们提到本次证明的情况为FAST : SLOW = 3 : 1。
  故每次移动FAST都会让其与SLOW的距离减少 2。
  如下表格体现:

当N为偶数时当N为奇数时
N - 2N - 2
N - 4N - 4
43
21
0(相遇)-1(第一次错过)

  我们发现当N为偶数时一定会相遇,当N为奇数时第一次FAST会与SLOW擦肩而过。
  此时我们再讨论第一次错过后的情形,假设环的一圈距离为C,当第一次错过时,FAST与SLOW在新一轮追逐过程中的距离为C - 1。

当C - 1为偶数时当C - 1为奇数时
C - 1 - 2C - 1 - 2
C - 1 - 4C - 1 - 4
43
21
0(相遇)-1(第二次错过)

  我们发现如果想让快慢指针在环中永远不会相遇,也就是FAST多指向的地址永远不会等于SLOW所指向的地址,那么就需要C - 1为奇数,且N也同时为奇数,此时我们使用反证法来证明快慢指针在带环链表中是否存在无法相遇的情形。

  假设C - 1 为奇数,那么C就为偶数,且同时N为奇数。

  而我们可以很轻松的得到,FAST在SLOW刚刚到达入环点时走过的路程为:

    3L = L + X * C + C - N
    通过简单的数学计算可以得到:
    2L = ( X + 1 ) * C - N

  令2L为A部分, ( X + 1 ) * C为B部分,N为C部分,显然A为偶数。

ABCB - C结果
偶数偶数奇数奇数等号不成立
偶数偶数偶数偶数等号成立
偶数奇数(此时要求C为奇数且X + 1为奇数)偶数奇数等号不成立
偶数奇数(此时要求C为奇数且X + 1为奇数)奇数偶数等号成立

  通过上表我们可以发现,当等号成立时不存在C为偶数,N为奇数的情形,故快慢指针在3 :1的速度比之下不存在永远无法相遇的情形。

2.2 加证

  为了证明更加严谨,我们加证一条FAST :SLOW = 4 :3的情形。

  我们可以得到,SLOW刚刚到达入环点时走过的路程为:
    3L

  FAST在SLOW刚刚到达入环点时走过的路程为:
    4L = 3L + X * C + C - N
    通过简单的数学计算可以得到:
    L = ( X + 1 ) * C - N

  FAST与SLOW的追赶路程为N

当N为偶数时当N为奇数时
N - 1N - 1
N - 2N - 2
22
11
0(相遇)0(相遇)

  故我们可以清楚的看到当FAST :SLOW = 4 :3 时,无论N为偶数还是N为奇数都一定会相遇。



3. 结论


  通过上文证明我们可以发现:
  当 FAST与SLOW速度差为偶数时,在等号成立的前提下,不同时存在C为偶数且N为奇数的情形,即当FAST与SLOW速度差为偶数时一定会相遇。
  当 FAST与SLOW速度差为奇数时,无论N为奇数还是偶数,都一定会相遇。
  故 不存在快慢指针在带环链表中无法相遇的情形,反证法得证。




4. 结语


  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
  如需引用,注明地址。

这篇关于【证明】快慢指针在带环链表中是否存在无法相遇的情形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/950033

相关文章

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

Java Optional避免空指针异常的实现

《JavaOptional避免空指针异常的实现》空指针异常一直是困扰开发者的常见问题之一,本文主要介绍了JavaOptional避免空指针异常的实现,帮助开发者编写更健壮、可读性更高的代码,减少因... 目录一、Optional 概述二、Optional 的创建三、Optional 的常用方法四、Optio

如何解决mmcv无法安装或安装之后报错问题

《如何解决mmcv无法安装或安装之后报错问题》:本文主要介绍如何解决mmcv无法安装或安装之后报错问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mmcv无法安装或安装之后报错问题1.当我们运行YOwww.chinasem.cnLO时遇到2.找到下图所示这里3.

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

SpringBoot项目启动报错"找不到或无法加载主类"的解决方法

《SpringBoot项目启动报错找不到或无法加载主类的解决方法》在使用IntelliJIDEA开发基于SpringBoot框架的Java程序时,可能会出现找不到或无法加载主类com.example.... 目录一、问题描述二、排查过程三、解决方案一、问题描述在使用 IntelliJ IDEA 开发基于