行业知识
C语言——环形链表详解
目录
- 什么是带环链表
- 检测链表是否带环
- fast和slow会不会错过
- 当fast走两步时
- 当fast走三步时
- 结论：
- 当fast走四步时
- 总结：
什么是带环链表
在一个单链表中，链表中存在环形结构。
在链表中的某个节点，可以连续通过next指针再次到达，则链表中存在环。
检测链表是否带环
我在最开始判断链表是否带环时，是这样一种思路：
通过连续跟踪next，看next能不能等于我标记的节点，如果等于，那么这就是一个带环链表。
这个方法并不可行，因为能不能再次走到标记的节点，在于标记的节点在不在环里，如果不在环里，那么就永远找不到。
有可能像上图一样很快就进环，也有可能像这样：
进环前的前缀比较长。
判断方法：
使用快慢指针：
快指针一次性往后走两个节点，慢指针一次走一个节点。
判断快指针和慢指针是否相遇，如果相遇，就代表链表中存在环。
画图更清晰：
代码也是非常简单：
bool hasCycle(struct ListNode *head) { ListNode* slow = head; ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(fast == slow) { return true; } } return false;}fast和slow会不会错过
为什么fast和slow一定会相遇，有没有可能错过，永远追不上？
当fast走两步时
我们这里先用fast走两步，slow走一步为例：
fast追击slow的过程中距离的变化如下：
N
N-1
N-2
……
2
1
0
也就是说，每追击一次，他们的距离就缩短1，直到距离为0追上。
——————————————————————————————————————————
如果slow走一步，fast走三步，四步，五步呢，还能追的上吗？
我们用同样的方法分析一下：
当fast走三步时
当fast进环时，fast和slow的距离为N
fast追击slow的过程中距离变化如下：
N为偶数：
N
N-2
N-4
……
4
2
0 (追上了)
——————————————————————————————————————————
N为奇数：
N
N-2
N-4
……
3
1
-1（错过了）
这里又要开始新一轮的追击。
我么假设环的长度为C
这时距离变成了N=C-1
结论：
当fast走两步时，一定能追上slow
当fast走三步时
- 如果N为偶数，直接追上
- 如果N为奇数，继续追击，这里还要再分成两个情况
1）C-1是偶数，就又回到了N为偶数的问题，新一轮追击将会追上
2）C-1是奇数，出现***循环，永远错过
——————————————————————————————————————————
当fast走四步时
fast追击slow的过程中距离变化如下：
- N为三的倍数
N
N-3
N-6
……
6
3
0（追上了）
——————————————————————————————————————————
- N不为三的倍数
a、N % 3 == 2
N
N-3
N-6
……
4
1
-2
那么这里又有两种情况：
C-2是偶数，就又回到了N为偶数的问题，新一轮追击将会追上
C-2是奇数，出现***循环，永远错过
b、N % 3 == 1
N
N-3
N-6
5
2
-1
那么这里还是有两种情况：
C-1是偶数，就又回到了N为偶数的问题，新一轮追击将会追上
C-1是奇数，出现***循环，永远错过
总结：
无论slow走几步，fast走几步，追击问题关系的不是走几步，而是速度差，因为他们最终都会进环。
我们回到原来的问题，fast和slow到底会不会错过。
当fast走三步，slow走一步时为例：
如果同时存在N是奇数且C是偶数，那么将永远追不上。但是，有没有一个可能，这种情况不存在。
我们使用数学来证明一下。
假设slow进环时fast跟slow的距离为N
slow走的距离为L
fast走的距离为L + xC + C - N（slow进环时，假设fast已经转了x圈）
因为fast走的距离时slow的三倍
3L = L + Cx + C - N
简化一下：
2L = Cx + C - N
2L = C*(x+1) - N
2乘任何数都为偶数，所以2L一定为偶数，上面说到：
“如果同时存在N是奇数且C是偶数，那么将永远追不上。但是，有没有一个可能，这种情况不存在。”
2L = C*(x+1) - N：
偶数 = (x+1) * 偶数 - 奇数
这种情况不可能存在！！！只有奇数减去奇数才能为偶数， “(x+1) * 偶数” 一定是偶数。
所以“N是奇数且C是偶数”不能同时存在，总会追击上的。
希望这篇博客对你有所帮助！！！
