快慢指针判断环形链表

简介: 快慢指针判断环形链表

我们在前面文章中写过用快慢指针判断链表是否带环:

leetcode:环形链表-CSDN博客

我们用的是slow指针一次走一步,fast指针一次走两步,当slow入环后开始了追击,每走一次距离缩短1,最终就会相遇

思考问题

但是我们思考一个问题:如果slow一次走一步,fast一次走三步,会不会相遇呢?

思考这个问题我们可以做一个假设:

假设环的长度是C,假设slow进环时,fast与slow之间的距离为N

推导思路

接着我们可以推一下:

如果slow一次走一步,fast一次走三步,每次追击距离缩小2

所以我们可以得出初步的结论:

  1. 如果N是偶数,就直接追上了
  2. 如果N是奇数,C是奇数,第一轮错过了,第二轮就追上了
  3. 如果N是奇数,C是偶数,就永远追不上

结论的第三条其实条件是不成立的,我们画图推一下:

所以这里我们就能得到一个结论

如果N是奇数,C是偶数,这个等式的条件是不成立的,所以不可能出第三种情况

结论

所以我们可以得出最终的结论:

  1. 如果N是偶数,就直接追上了
  2. 如果N是奇数,C是奇数,第一轮错过了,第二轮就追上了
  3. 不可能出现N是奇数,C是偶数的情况

所以如果slow一次走一步,fast一次走三步,一定能追上

相关文章
|
5天前
教你三指针拿捏链表翻转
教你三指针拿捏链表翻转
|
5天前
|
索引
【力扣】142. 环形链表 II
【力扣】142. 环形链表 II
|
5天前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
|
5天前
数据结构--链表刷题(一)快慢指针(下)
数据结构--链表刷题(一)快慢指针
15 0
|
5天前
数据结构--链表刷题(一)快慢指针(上)
数据结构--链表刷题(一)快慢指针
16 0
|
5天前
|
算法 C语言 索引
环形链表(快慢指针)
环形链表(快慢指针)
|
5天前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
32 0
|
5天前
|
算法 Java
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战
29 0
|
5天前
|
C语言
C语言:数组和指针笔试题解析(包括一些容易混淆的指针题目)
C语言:数组和指针笔试题解析(包括一些容易混淆的指针题目)
|
5天前
|
存储 程序员 编译器
爱上C语言:指针很难?来来来,看看这篇(基础篇)
爱上C语言:指针很难?来来来,看看这篇(基础篇)