目录
前言
一、为什么快指针每次⾛两步，慢指针⾛⼀步可以相遇，有没有可能遇不上
二、快指针⼀次⾛3步，⾛4步，...n步⾏吗?
三、求环形链表中入环的节点
前言
在学习链表的时候我发现一个一个非常有趣的问题链表带环，可能大部分人都知道使用快慢指针来解决链表带环问题
快慢指针解决链表带环问题
慢指针⼀次⾛⼀步，快指针⼀次⾛两步，两个指针从链表起始位置开始运⾏， 如果链表 带环则⼀定会在环中相遇，否则快指针率先⾛到链表的未尾
//链表带环
bool hasCycle(struct ListNode* head)
{
if (head == NULL || head->next == NULL)
{
return false;
}
//快指针，一次走2步
struct ListNode* k = head;
//慢指针，一次走1步
struct ListNode* m = head;
while (k != NULL && k->next != NULL)
{
k = k->next->next;
m = m->next;
//相遇
if (k == m)
{
return true;
}
}
//跳出循环表示，未带环
return false;
}题目链接
141. 环形链表 - 力扣（LeetCode）
那这里大家是否思考过一下这两个问题，或者是否会有一下这两个问题
1、为什么快指针每次⾛两步，慢指针⾛⼀步可以相遇，有没有可能遇不上
2、快指针⼀次⾛3步，⾛4步，...n步⾏吗?
这里先做一个总结
快指针每次⾛两步，慢指针⾛⼀步一定可以相遇
如果N是偶数，第⼀轮就追上了如果 N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击C-1如果是偶数，那么下⼀轮就追上了C-1如果是奇数， 那么就永远都追不上
一、为什么快指针每次⾛两步，慢指针⾛⼀步可以相遇，有没有可能遇不上
假设slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为N，接下来开始追逐
因为 fast 一次走2步， slow 一次走1步，相差1步，追逐过程中，每追击⼀次，他们之间的距离缩⼩1步
追击过程中fast和slow之间的距离变化：
fast和slow之间的距离：N
fast和slow之间的距离：N - 1
fast和slow之间的距离：N - 2
fast和slow之间的距离：N - 3
fast和slow之间的距离：N - 4
fast和slow之间的距离：N - 4
fast和slow之间的距离：........
fast和slow之间的距离：N - N
fast和slow之间的距离：0
因此快指针每次⾛两步，慢指针⾛⼀步一定可以相遇
二、快指针⼀次⾛3步，⾛4步，...n步⾏吗?
假设头节点到入环的距离为L，环的周长为C，slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为N，fast 和slow之间的相差距离为C - N，接下来开始追逐
按照上⾯的分析，fast 一次走3步， slow 一次走1步，相差2步，追逐过程中，每追击⼀次，他们之间的距离缩⼩2步
追击过程中fast和slow之间的距离变化：
情况一： 情况二：
fast和slow之间的距离：N fast和slow之间的距离：N
fast和slow之间的距离：N - 2 fast和slow之间的距离：N - 2
fast和slow之间的距离：N - 4 fast和slow之间的距离：N - 4
fast和slow之间的距离：N - 6 fast和slow之间的距离：N - 6
fast和slow之间的距离：N - 8 fast和slow之间的距离：N - 8
fast和slow之间的距离：N - 10 fast和slow之间的距离：N - 10
fast和slow之间的距离：........ fast和slow之间的距离：..........
fast和slow之间的距离：N - N fast和slow之间的距离：N - N - 1
fast和slow之间的距离：0 fast和slow之间的距离：-1
当fast和slow之间的距离为-1时，意味着fast反超了slow，进入了新一轮的追逐，此时fast和slow之间的距离为C - 1，（ C为环的周长 ）
当fast于slow进入新的一轮追逐时C-1如果是偶数，那么下⼀轮就追上了，C-1如果是奇数， 那么就永远都追不上，这里我们用公式证明
在追逐过程中，慢指针到入环点时所⾛的路径⻓度:
fast: L + xC + C - N（ x 表示快指针在环中走了 x 圈）
（ 节点到入环的距离 + fast在环中走了多少圈 + fast 和slow之间的相差距离 ）
slow：L
（ 节点到入环的距离 ）
由于慢指针⾛⼀步，快指针要⾛三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即：
3L = L + xC + C - N
2L = （x + 1）C - N
由于偶数乘以任何数都为偶数，因此 ⼀定为偶数，则可推导出可能得情况：
情况1：偶数 = 偶数 - 偶数情况2：偶数 = 奇数 - 奇数结论如果N是偶数，则第⼀圈快慢指针就相遇了如果N是奇数，则fast指针和slow指针在第⼀轮的时候套圈了，开始进⾏下⼀轮的追逐；当N是奇数，要满⾜以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数
快指针⼀次⾛4、5.....步最终也会相遇，其证明⽅式同上
三、求环形链表中入环的节点
这个问题也是环形链表中一个非常经典的问题，同样的也是通过使用快慢指针来解决，快指针一次走2步，慢指针一次走1步，首先给出结论
快慢指针的相遇点 于 头节点 到入环的距离是相等的
//寻找快慢指针的相遇点
struct ListNode* search(struct ListNode* head)
{
struct ListNode* m = head;
struct ListNode* k = head;
while (k != NULL && k->next != NULL)
{
m = m->next;
k = k->next->next;
if (k == m)
{
return k;
}
}
return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{
//寻找快慢指针的相遇点
struct ListNode* meet = search(head);
if (meet == NULL)
{
return NULL;
}
//快慢指针的相遇点 与 头节点 到入环的距离是相等的
struct ListNode* m = head;//头节点
struct ListNode* k = meet;//相遇点
//相遇点与头节点同时向前走，直到相遇为止
while (k != m)
{
m = m->next;
k = k->next;
}
return k;
}题目链接
证明
假设头节点到入环的距离为L，环的周长为C，slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为 C - N，fast 和slow之间的相差距离为N
当快慢指针相遇时所⾛的路径⻓度:
fast: L + xC + N（ x 表示快指针在环中走了 x 圈）
（ 节点到入环的距离 + fast在环中走了多少圈 + fast 和slow之间的相差距离 ）
slow：L + N
（ 节点到入环的距离 + fast 和slow之间的相差距离 ）
【注意】
当慢指针进⼊环时，快指针可能已经在环中绕了x圈了，x⾄少为1
慢指针进环之后，快指针肯定会在慢指针⾛⼀圈之内追上慢指针
由于慢指针⾛⼀步，快指针要⾛两步，因此得出： 2 * 慢指针路程 = 快指针路程 ，即：
2(L + N) = L + xC + N
L + N = xC
L = xC - N
L = (x - 1)C + C - N
(x为1,2,3,4......，x的⼤⼩取决于环的⼤⼩，环越⼩x越⼤)
取极端情况表示快指针在环中走了 1 圈，即 x = 1
L = C - N
1、L为头节点到入环点的距离
2、C - N为fast 和slow之间的距离，即相遇点到入环的距离
由此可以证明：快慢指针的相遇点 于 头节点 到入环的距离是相等的
![[电子科大]王丽杰 离散数学 第二讲 特殊集合和集合间关系 笔记](https://i-blog.csdnimg.cn/direct/a0b6526818cf4e7580265706692c30b3.png)
![[前端] ✨【如何用课程设计提升工程能力？】✨笔记](https://i-blog.csdnimg.cn/direct/3ab1c49aa4fd4e6ab549c2475b50124a.jpeg)
