一、先搞懂什么是链表有环正常链表是一条直线1 → 2 → 3 → 4 → 5 → NULL有环的链表尾巴会指回前面某个节点形成一个圈1 → 2 → 3 → 4 → 5 → 6 → 回到 3这样永远走不到头就是带环链表。我们的目标找到这个环的入口节点例子里是 3。二、核心思路整个算法分为3 个关键步骤逻辑非常清晰判断链表有没有环算出环里有多少个节点用 “先走环长步” 的方法找到入口三、第一步先快慢指针判断有环这是最经典的快慢指针法快指针 fast每次走2 步慢指针 slow每次走1 步如果链表无环fast 会走到 NULL如果链表有环fast 一定会在环里追上 slow两者相遇原理很简单快指针速度是慢指针的 2 倍进环后迟早会 “套圈” 追上。四、第二步计算环的节点个数当快慢指针相遇后固定 slow 不动让 fast 继续一步步走每走一步计数当 fast 再次回到 slow 时统计的总数就是环的长度在我们的例子里环长 6 个节点。五、第三步先走环长步再同步走(关键点)这是找到入口的核心思想把 fast 和 slow重新回到链表头节点让fast 先走 “环长” 步我们这里是先走 6 步然后 fast 和 slow以相同速度每次都走 1 步它们相遇的地方就是环的入口为什么这样能找到入口快指针先走环长步相当于提前绕环一圈之后两者同步前进距离刚好完美匹配当慢指针走到环入口时快指针也刚好走到这里六、核心代码// 找到环的入口节点 Node* findBegin(Node *head) { Node *fast head; Node *slow head; // 1. 快慢指针相遇判断有环 while(fast ! NULL fast-next ! NULL) { fast fast-next-next; slow slow-next; if (fast slow) { // 2. 计算环的节点数 int count 1; while(fast-next ! slow) { count; fast fast-next; } // 3. 重新指向头节点 fast head; slow head; // fast 先走 count 步 for (int i 0; i count; i) { fast fast-next; } // 同步走相遇就是入口 while(fast ! slow) { fast fast-next; slow slow-next; } return slow; } } return NULL; }七、完整可运行完整代码#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* initList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; return head; } Node* insertTail(Node *tail, int data) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data data; newNode-next NULL; tail-next newNode; return newNode; } // 核心函数 Node* findBegin(Node *head) { Node *fast head; Node *slow head; while(fast ! NULL fast-next ! NULL) { fast fast-next-next; slow slow-next; if (fast slow) { int count 1; while(fast-next ! slow) { count; fast fast-next; } fast head; slow head; // fast 先走环长步 for (int i 0; i count; i) { fast fast-next; } while(fast ! slow) { fast fast-next; slow slow-next; } return slow; } } return NULL; } int main() { Node *list initList(); Node *tail list; tail insertTail(tail, 1); tail insertTail(tail, 2); tail insertTail(tail, 3); Node *enter tail; // 环入口 tail insertTail(tail, 4); tail insertTail(tail, 5); tail insertTail(tail, 6); tail insertTail(tail, 7); tail insertTail(tail, 8); // 构造环8 → 3 tail-next enter; Node *res findBegin(list); printf(环的入口节点是%d\n, res-data); return 0; }八、运行结果九、算法总结这套方法的核心思想可以浓缩成三句话快慢指针相遇 链表有环相遇点绕一圈 算出环长快指针先走环长步再同步走 找到环入口时间复杂度 O (n)空间复杂度 O (1)是最优解法。