题目描述
题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目分析
我们假设起点到环的入口点的距离是L，入口点到相遇点的距离是X，环的长度是C
那么画图我们可以得知：
- 从开始到相遇时slow走的距离是L+X
- 从开始到相遇时fast走的距离是L+n*C+X
（n:slow进环前，fast已经在环里走了 n 圈）
由于fast=slow*2，所以我们可以得到结论：一个指针从相遇点开始走，一个指针从头开始走，最终会在入口点相遇
我们可以画图来证明一下：
代码示例
根据这个思路我们可以写出代码:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow,* fast; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast)//相遇 { struct ListNode *meet=slow; while(head!=meet) { head=head->next; meet=meet->next; } return meet; } } return NULL; }
结果当然也是通过了
