引言
环形链表问题是数据结构与算法中的经典问题，在面试中出现频率极高。这类问题不仅考察对链表结构的理解，更考验解决问题的思维能力和数学分析能力。本文将详细分析环形链表的判断方法以及环入口节点的定位算法。
环形链表判断
问题描述
给定一个链表的头节点 head，判断链表中是否存在环。
解决方案：快慢指针法
快慢指针法是解决环形链表问题的经典方法，其核心思想是使用两个指针以不同速度遍历链表。
bool hasCycle(struct ListNode* head) {
struct ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
// 一定要先让快慢指针走，再判断，因为一开始快慢指针都是 head
if (slow == fast) return true;
}
return false;
}
原理分析
为什么快慢指针一定能相遇？
假设慢指针进入环时，快指针与慢指针之间的距离为 N。由于快指针每次比慢指针多走一步，它们之间的距离会逐次减少：N, N-1, N-2, …, 2, 1, 0。因此最终一定会相遇。
步长选择的数学分析
为什么选择一步和两步？
当快指针每次走三步、四步或更多时，情况会变得更加复杂。以三步为例：
- 每次移动后，快慢指针之间的距离减少 2
- 当 N 为偶数时，可以追上
- 当 N 为奇数时，会错过，距离变为 C-1（C 为环长）
假设 slow 进环时，fast 跟 slow 的距离是 N。
fast 追击 slow 时 距离变化为 N N-1 N-2 ……2 1 0 所以能追上
当 fast 等于 3 时，每次 fast 与 slow 距离就减 2。
- 当 N 为偶数时，可以追上
- 当 N 为奇数时，会错过，这时他们的距离会变为 C-1（假设 C 为环的长度） a. 如果 C-1 为偶数 (C 为奇数)，下一轮就追上了 b. 如果 C-1 为奇数 (C 为偶数)，就永远追不上
所以这么一看，追不上的条件是：N 为奇数并且 C 为偶数。
但是这种情况存在吗？
进一步分析表明，当快指针走三步时，追不上的条件是：N 为奇数且 C 为偶数。但通过数学推导可以证明这种情况实际上不可能发生：
假设 slow 走的距离是 L fast 走的距离就是 L+x*C+N (x 为 fast 走的圈数) fast 走的距离是 slow 的 3 倍
3L = L + xC + N 化简可得 2L = xC + N
当 C 为偶数 N 为奇数时，x*C 为偶数 等号左边是偶数，右边是偶数加奇数（也就是奇数），显然不成立 所以不存在 N 为奇数，C 为偶数的情况 所以 fast 一定能追上 slow
环形链表Ⅱ
题目如下
方法一
找到 fast 与 slow 相遇的位置 meet，head 与 meet 同时走，他们相遇位置就是环的入口。
证明如下：
相遇时: slow 走的路程为：L+N fast 走的路程为：L+x*C+N fast 走的是 slow 的 2 倍
2(L+N) = L + x*C + N 化简可得 L = (x-1)*C + C - N
所以 L 的长度就是相遇点转了 x-1 圈 再走了 C-N 距离的点 这意味着：从头节点到环入口的距离 L，等于从相遇点走 (x-1) 圈再加 (C-N) 步。因此，两个指针分别从头节点和相遇点出发，一定会在环入口相遇。
代码如下
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
struct ListNode* meet = slow;
while (meet != head) {
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
方法二：转换为相交链表问题
算法思路
- 找到快慢指针的相遇点
- 将环从相遇点处断开
- 问题转换为求两个链表的交点问题
将环形链表断开 newhead = meet->next meet->next = NULL 这样就转换成了链表相交的问题
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* curA = headA, *curB = headB;
int lenA = 1, lenB = 1;
while (curA->next) { curA = curA->next; lenA++; }
while (curB->next) { curB = curB->next; lenB++; }
int gap = abs(lenA - lenB);
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if (lenA < lenB) { longList = headB; shortList = headA; }
while (gap--) { longList = longList->next; }
while (longList) {
if (longList == shortList) return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
struct ListNode* meet = slow;
struct ListNode* newhead = meet->next;
meet->next = ;
getIntersectionNode(head, newhead);
}
}
;
}
实际应用与扩展
应用场景
- 内存管理：检测内存泄漏或循环引用
- 状态机检测：验证有限状态机是否会进入循环状态
- 递归检测：判断递归函数是否会无限递归
- 哈希冲突解决：在开放定址法中检测哈希表是否已满
