💡题目分析

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。

在这里插入图片描述

💡解题思路

先使用快慢指针找到相遇点（定义两个指针，一个快指针、一个慢指针，让快指针一次走一步，慢指针一次走两步，如果存在环的话，快指针会先进环，一直在环中循环的走，等到慢指针也进入环中循环，快指针追击慢指针，最后它们一定会相遇，找到相遇点），然后一个指针从相遇点开始走，一个指针从链表头开始走，最终他们会在入口点相遇

💡深度思考

fast走的路程是slow的2倍

假设：
链表头 ---- 环入口点的距离：L
环入口点 ---- 相遇点的距离：X
环的长度：C
slow走的路程是多少？

slow走的路程为：L+X

分析：有没有可能slow进环转了几圈才追上？

不可能！1圈之内，fast必然追上slow，因为他们之间距离每次缩小1，不会错过，slow走1圈，fast都已经走2圈了，肯定追上了。

fast走的路程是多少？

fast走的路程为：L+C+X ?

✅fast走的路程应该为：L + n*C + X
假设n是slow进环前，fast在环里面转的圈数

🔔接口源码

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(head != meet){head = head->next;meet = meet->next;}return meet;}}return NULL;
}