【数据结构与算法】环与相遇：链表带环问题的底层逻辑与工程实现
前言
链表带环问题是数据结构中的经典考点，核心在于通过快慢指针法判断环的存在并定位入口点。本文从 LeetCode 两道真题出发，拆解快慢指针的相遇逻辑与数学推导，结合代码实现与严谨证明，清晰呈现带环链表的解题思路，帮助读者深入理解指针策略在链表问题中的灵活运用。
一、带环 链表
1.1题目
链接：带环链表
注：这道题我们依旧使用高阶要求来做题
1.2 算法 原理
核心思想: 快慢指针 --- 相遇即为链表带环
创建两个指针 — slow和fast初始指向head,遍历链表slow每次走一步，fast每次走两步，那么就会分成两种情况：
• 链表不带环：那么fast一定可以遍历到NULL，
•链表带环：fast一定比slow先走进循环，在环内不断循环，当slow也进入循环时，如果链表带坏则与fast必定能相。
1.3 代码
/** * 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; }
1.4 数学 证明
1.4.1 为什么带环slow与fast必定能相遇？
假设slow进环时与fast的差距为N，那么接下来就是追击问题，slow每次走一步，fast每次走两步。那么每走完一次slow的距离就会变成：N - 1，N - 2，N -3…2,1,0，故必定会相遇
1.4.2 fast一定只能走2步吗？可以是2步甚至更多吗？
1.4.2.1 以3步为例
假设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始终满足：slow = 2 * fast。
联立上面三个式子可得：2L = (x+ 1) * C - N ,我们分析可得该等式为：偶数 = （x + 1） 偶数 - 奇数不成立，故两个条件无法同时成立 ，故不会永远追不上，slow和fast必定相遇，
1.4.3结论
• 链表带环，使用快慢指针，无论fast走几步，都必定在环内与slow相遇。
二、环形链表（寻找相遇点）
2.1 题目
链接：环形链表（寻找相遇点）
2.2 算法原理
2.3 代码
/** * 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; }
2.4 数学证明
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即：一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在入口点的位置相遇
2.4.1 结论
• 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
