DAY 4.链表中环的入口节点

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、链表中环的入口节点
• 二、代码实现
• • 2.结论
• 总结

---

前言

`

---

一、链表中环的入口节点

思路：使用快慢指针，都从头节点出发，快指针一次走两步，慢指针一次走一步，如果有环的话，他们一定会相遇。
找环入口的方法：将一个指针放在头节点，另一个指针在相遇的位置，既保持不变，然后同时让他们一次走一步，找到他们相遇的节点，那个点就是环的入口。

二、代码实现

代码如下（示例）：

structListNode*EntryNodeOfLoop(structListNode*pHead){structListNode*fast=pHead;structListNode*slow=pHead;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow){break;}}if(fast==NULL||fast->next==NULL){returnNULL;}slow=pHead;while(slow!=fast){slow=slow->next;fast=fast->next;}returnslow;}

2.结论

当快慢指针在环里相遇后：
把 慢指针放回链表头部
两个指针现在都一次只走 1 步
它们再次相遇的地方，就是环的入口！

---

总结

快慢指针相遇 = 有环
一个回头，一个留原地
同速走，相遇点 = 环入口
原因就是：
头到入口的距离 = 相遇点到入口的距离