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

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

相关文章

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 开发基于

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Android WebView无法加载H5页面的常见问题和解决方法

《AndroidWebView无法加载H5页面的常见问题和解决方法》AndroidWebView是一种视图组件,使得Android应用能够显示网页内容,它基于Chromium,具备现代浏览器的许多功... 目录1. WebView 简介2. 常见问题3. 网络权限设置4. 启用 JavaScript5. D

SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法

《SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法》本文主要介绍了SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法,具有一定的参考价值,感兴趣的可以了解一下... 目录方法1:更改IDE配置方法2:在Eclipse中清理项目方法3:使用Maven命令行在开发Sprin

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D