朋友们、伙计们，我们又见面了，本期来给大家解读一下LeetCode中第142道单链表OJ题，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！
数据结构与算法专栏：数据结构与算法
个 人 主 页 ：stackY、
C 语 言 专 栏：C语言：从入门到精通
编辑
LeetCode--142.环形链表Ⅱ： https://leetcode.cn/problems/linked-list-cycle-ii/description/
目录
1.题目介绍
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
编辑
2.实例演示
编辑
3.解题思路
小编在这里给大家推荐比较简单的解题思路，同样的都是使用快慢指针的，我们先来讲具体的解题思路，后面会验证这种方法的正确性：
同样的还是设置快慢指针，慢指针一次走一步，快指针一次走两步，同样的我们先来判断链表是否有环（如何判断链表有环大家可以去看LeetCode：141.环形链表这篇博客，里面包含了具体解题思路），在判断是否有环之后呢，我们要找到第一次入环的节点，那这个就比较麻烦了，该怎么找呢？小编在这里给大家提供一个简单的解法：记录环中快慢指针相遇的节点（meet），然后让一个指针从链表的头（head）开始走，一次都走一步，当meet和head相遇时它们就是第一次入环的节点。
代码演示：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { //设置快慢指针 struct ListNode* slow = head; struct ListNode* fast = head; //快慢指针的相遇节点 struct ListNode* meet = NULL; //判断是否有环 while(fast && fast->next) { fast = fast->next->next; slow = slow->next; //若有环则记录快慢指针的相遇节点 if(fast == slow) { meet = slow; //找第一次入环的节点 while(meet != head) { //一次都走一步 meet = meet->next; head = head->next; } return meet; } } //无环则返回NULL return NULL; }
4.思路验证
要求环形链表第一次入环的节点，我们使用的这种快慢指针的方法是很简单的，也是很巧妙的，这种方法具体是怎么实现的，让我们接着往下来看：
我们假设环的长度为C，链表的头到第一次入环节点的距离为L，第一次入环的节点到相遇点的距离为X。
编辑
慢指针在这里有一个分析问题：slow有没有可能在环里面转了好几圈快指针才追上？
答案是肯定不可能，因为快指针的速度是慢指针的2倍，不存在错过的情况，所以慢指针不存在走好几圈才能被快指针追上的情况。
很多老铁在这里验证的时候使用了一种错误的验证方法：
慢指针slow走的路程是：L + X
快指针fast走的路程是：L + X + C
那么就有一种对应的关系：2 * （L + X） = L + X + C
L = C - X
这种方法有一个弊端，比如一个环形链表前面进环的路程(L)非常的长，而环(C)又非常的小，那这就出现问题了：
编辑
所以呢我们可以将这种特殊的情况考虑进去，那么我们应该先算快指针fast走的路程：
快指针fast走的路程：L + n * C + X（n为慢指针进环之前快指针在环里面走过的圈数）
慢指针slow走的路程是：L + X
那么就有一种对应的关系： 2 * （L + X） = L + X + n * C
L = n * C - X
那么这样解释起来就好多了，相遇节点到第一次入环的节点的距离为C - X
头节点到第一次入环节点的距离为L，那么根据 L = n * C - X这个对应关系，就可以推出从相遇节点每次走一步，头指针每一次走一步，当它们两个相遇的时候就是这个环形链表第一次入环的节点。
编辑
5.其他解题方法
除了上面我们验证的这个方法外，还有另外的一种方法，小编在这里只说思路，感兴趣的老铁可以自己尝试一下：
分割环形链表法：
可以记录快慢指针的相遇节点，然后以这个相遇点为起点，保存并记录相遇节点的下一个节点，然后将相遇节点和它的下一个节点断开链接，将这个环一分为二，这时就转换成了链表相交的问题。
一个链表是从头开始，另一个链表的头是从相遇点的下一个节点，那么这两个链表的相交节点就是第一次入环的节点。
编辑
感兴趣的老铁可以自己动手写一下完整的代码。
朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！
