技术博客：判断链表是否有环并返回环的起始结点
引言
在链表操作中，判断链表是否存在环形结构是一个常见的问题。本文将详细介绍如何使用快慢指针法判断链表是否有环，并进一步找到环的起始结点。我们将分步骤讲解每一步的实现原理，并提供完整的代码实现。
1. 题目解读
题目要求：判断一个链表中是否存在环形结构，并返回环形结构的起始结点。
链表节点结构定义如下：
struct ListNode {
int val;
struct ListNode *next;
};
2. 解题思路
2.1 判断链表是否有环
使用快慢指针法判断链表是否有环。快指针 fast 每次移动两步，慢指针 slow 每次移动一步。如果存在环，快指针和慢指针最终会在环内相遇。
2.2 寻找环的起始结点
一旦确定链表存在环，我们需要找到环的起始结点。假设链表的头节点到环的起始结点的距离为 a，环的长度为 c，快指针和慢指针在环内的某个点相遇，慢指针已经走了 a + b 步，快指针已经走了 a + b + k * c 步（其中 k 是快指针在环内绕的圈数）。
根据快慢指针的速度关系，可以得出以下方程：
[ 2(a + b) = a + b + k / c ]
简化方程：
[ a + b = k /c ]
从第一个方程可以推出：
[ a + b = k / c ]
从第二个方程可以推出：
[ a = (k - 1) / c + (c - b) ]
这表明从头节点开始走 a 步和从相遇点开始走 c - b 步会到达同一个位置，即环的起始结点。
3. 具体代码实现
3.1 判断链表是否有环
struct ListNode* hasCycle(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return slow; // 相遇点
}
}
return NULL; // 无环
}
详细解释：
- 初始条件：
slow和fast都指向链表的头部。 - 移动条件：
fast每次移动两步，slow每次移动一步。 - 终止条件：如果
fast到达链表末尾（fast == NULL或fast->next == NULL），则链表无环。如果slow和fast相遇，则链表有环。
3.2 寻找环的起始结点
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode *meetNode = hasCycle(head);
if (meetNode == NULL) {
return NULL; // 无环
}
struct ListNode *startNode = head;
struct ListNode *currentNode = meetNode;
while (startNode != currentNode) {
startNode = startNode->next;
currentNode = currentNode->next;
}
return startNode; // 环的起始结点
}
详细解释：
- 初始条件：
startNode指向链表头部，currentNode指向相遇点。 - 移动条件：
startNode和currentNode每次各移动一步。 - 终止条件：当
startNode和currentNode相遇时，返回startNode，即环的起始结点。
3.3 完整代码
#include <stdio.h>
// 定义链表节点结构
struct ListNode {
int val;
struct ListNode *next;
};
// 判断链表是否有环
struct ListNode* hasCycle(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return slow; // 相遇点
}
}
return NULL; // 无环
}
// 寻找环的起始结点
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode *meetNode = hasCycle(head);
if (meetNode == NULL) {
return NULL; // 无环
}
struct ListNode *startNode = head;
struct ListNode *currentNode = meetNode;
while (startNode != currentNode) {
startNode = startNode->next;
currentNode = currentNode->next;
}
return startNode; // 环的起始结点
}
// 测试函数
int main() {
// 创建测试链表 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环)
struct ListNode *node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
node1->val = 1;
node1->next = node2;
node2->val = 2;
node2->next = node3;
node3->val = 3;
node3->next = node4;
node4->val = 4;
node4->next = node5;
node5->val = 5;
node5->next = node3; // 形成环
struct ListNode *cycleStart = detectCycle(node1);
if (cycleStart != NULL) {
printf("环的起始结点值为: %d\n", cycleStart->val);
} else {
printf("链表无环\n");
}
// 释放内存
free(node1);
free(node2);
free(node3);
free(node4);
free(node5);
return 0;
}
4. 注意事项
- 边界条件：
- 如果链表为空或只有一个节点，直接返回
NULL。 - 如果链表无环，返回
NULL。
- 如果链表为空或只有一个节点，直接返回
- 内存管理：
- 确保在测试完成后释放动态分配的内存，避免内存泄漏。
5. 寻找环起始节点的数学方法详解
5.1 快慢指针相遇点的数学推导
假设链表的头节点到环的起始结点的距离为 a，环的长度为 c，快指针和慢指针在环内的某个点相遇，慢指针已经走了 a + b 步，快指针已经走了 a + b + k * c 步（其中 k 是快指针在环内绕的圈数）。
根据快慢指针的速度关系，可以得出以下方程：
[ 2(a + b) = a + b + k / c ]
简化方程：
[ a + b = k / c ]
从第一个方程可以推出：
[ a + b = k / c ]
从第二个方程可以推出：
[ a = (k - 1) / c + (c - b) ]
这表明从头节点开始走 a 步和从相遇点开始走 c - b 步会到达同一个位置，即环的起始结点。
5.2 为什么从头节点和相遇点同时移动会相遇在环的起始结点
假设从头节点开始走 a 步到达环的起始结点，从相遇点开始走 c - b 步也会到达环的起始结点。因为 a 和 c - b 的总和都是环的长度 c 的整数倍加上从环的起始结点到相遇点的距离 b。
因此，从头节点和相遇点同时移动，每次各移动一步，最终会在环的起始结点相遇。
6. 总结
本文详细介绍了如何判断一个链表中是否存在环形结构，并找到环的起始结点。通过使用快慢指针法和数学分析，我们可以高效地实现这一功能。希望这篇博客对你有所帮助！如果有任何问题或需要进一步的解释，请随时提问。
