C++算法
链表带环检测与入口定位：快慢指针法原理及实现
链表带环检测利用快慢指针遍历，若存在环则必在环内相遇。通过数学推导证明无论步长如何设定，只要速度差固定且为整数倍，最终必然相遇。确定相遇点后，利用双指针同步移动可定位环的入口节点。该方法时间复杂度 O(n)，空间复杂度 O(1)，是解决此类问题的经典算法方案。
链表带环检测利用快慢指针遍历，若存在环则必在环内相遇。通过数学推导证明无论步长如何设定，只要速度差固定且为整数倍，最终必然相遇。确定相遇点后，利用双指针同步移动可定位环的入口节点。该方法时间复杂度 O(n)，空间复杂度 O(1)，是解决此类问题的经典算法方案。
链表带环问题是数据结构中的经典考点，核心在于通过快慢指针法判断环的存在并定位入口点。本文从 LeetCode 两道真题出发，拆解快慢指针的相遇逻辑与数学推导，结合代码实现与严谨证明，清晰呈现带环链表的解题思路。
链接：带环链表
核心思想: 快慢指针 --- 相遇即为链表带环
创建两个指针 — slow 和 fast 初始指向 head，遍历链表 slow 每次走一步，fast 每次走两步，那么就会分成两种情况： • 链表不带环：那么 fast 一定可以遍历到 NULL。 • 链表带环：fast 一定比 slow 先走进循环，在环内不断循环，当 slow 也进入循环时，如果链表带环则与 fast 必定能相遇。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode* ListNode;
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;
}
假设 slow 进环时与 fast 的差距为 N，那么接下来就是追击问题，slow 每次走一步，fast 每次走两步。那么每走完一次 slow 的距离就会变成：N - 1，N - 2，N - 3…2,1,0，故必定会相遇。
假设 slow 进环时与 fast 的差距为 N，那么接下来就是追击问题，slow 每次走一步，fast 每次走三步。会分成两种情况: • 当 N 是偶数时：N - 2，N - 4，N - 6…4，2，0 • 当 N 是奇数时：N - 2，N - 4，N - 6…3，1，-1
也就是当 N 是偶数时，必定会相遇，当 N 是奇数时最后距离为 -1，也就是会错过，如果假设圆环周长为 C，那么当 N 是奇数时且 fast 与 slow 错过后进入新一轮追击，距离变为 C-1，那么又会变成两个的情况： • 当 N = C -1 是偶数时 (C 为奇数)：N - 2，N - 4…4，2，0 • 当 N = C - 1 是奇数时 (C 为偶数）：N - 2，N - 4…3，1，-1 综上我们可以分析出要让 slow 和 fast 不相遇只有一种可能：C 为偶数且第一轮追击中 N 为奇数同时成立。 C 为偶数且第一轮追击中 N 为奇数能同时满足吗？ 那我们还是假设当 slow 进环时，slow 与 fast 相距 N: slow 走过的距离：L。 fast 走过的距离为：L + C * x(x:为绕环圈数) + C - N。 slow 与 fast 始终满足：fast = 2 * slow。 联立上面三个式子可得：2L = (x+ 1) * C - N ,我们分析可得该等式为：偶数 = （x + 1） 偶数 - 奇数不成立，故两个条件无法同时成立，故不会永远追不上，slow 和 fast 必定相遇。
• 链表带环，使用快慢指针，无论 fast 走几步，都必定在环内与 slow 相遇。
链接：环形链表（寻找相遇点）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode* ListNode;
struct ListNode *detectCycle(struct ListNode *head){
ListNode slow = head;
ListNode fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
ListNode meet = slow;
while(meet != head){
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
H 为链表的起始点，E 为环入口点，M 与判环时候相遇点 设：环的长度为 R，H 到 E 的距离为 L，E 到 M 的距离为 X 则：M 到 E 的距离为 R - X。在判环时，快慢指针相遇时所走的路径长度: fast: L + X + nR slow: L + X
注意： 当慢指针进入环时，快指针可能已经在环中绕了 n 圈了，n 至少为 1 因为：快指针先进环走到 M 的位置，最后又在 M 的位置与慢指针相遇 慢指针进环之后，快指针肯定会在慢指针走一圈之内追上慢指针。 因为：慢指针进环后，快慢指针之间的距离最多就是环的长度，而两个指针在移动时，每次它们之间的距离都缩减一步，因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。
极端情况下，假设 n = 1，此时：L=R−X 即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇
• 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online