一、问题描述
原题链接 142. 环形链表 II - 力扣（Le142. 环形链表 II - 力扣（Le
二、解题思路
方法一：数学公式推导法
预备知识
此方法的数学推导建立在判断链表是否带环的基础算法上，推荐阅读前置文章
点击下方文字
如图，通过快慢指针法得到两个指针相遇位置时 
假设：
- 链表入环前的长度为L
- 环的长度为C
- 快慢指针相遇节点为meet
- 环的入口与相遇节点meet的距离为N
- 相遇时，快指针已经在环内走了X圈（X>=1，快指针至少比慢指针都走一圈才能追上）
推导过程：
在meet相遇点
慢指针移动距离为L+N
快指针移动距离为L+X*C+N
另外，快指针移动距离是快指针的两倍
快指针也可以写成2（L+N）
将两条公式结合起来
2（L+N）=L+X*C+N
化简
L+N=X*C
L=X*C-N
L=（X-1）*C+C-N
最终得到的公式：
L=（X-1）*C+C-N
该公式在图中说明的问题：
链表入环前的长度L
与相遇点到环入口的距离再加（X-1）圈 ——X最少为1，所以X-1至少为0
是相等的
结论：
如果两个指针分别从链表起始位置和相遇点meet开始移动，那么两个指针第一次相遇的节点就是环的入口
方法二：转换为相交链表问题求解
此方法的数学推到建立在判断链表是否带环的基础算法上，推荐阅读
该方法是将带环链表问题转换为相交链表问题，将问题降级处理
首先，依然要 求得快慢指针相遇交点 
然后将取得该节点下一个节点地址，令其成为一个单独链表的首节点，断开链表
之后，这个问题就可以转换为相交链表问题来解决
三、代码实现
方法一实现代码
struct ListNode { int val; struct ListNode* next; }; typedef struct ListNode ListNode; //方法一：数学推理法 struct ListNode* detectCycle1(struct ListNode* head) { ListNode* slow, * fast; slow = fast = head; ListNode* meet = NULL; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast)//先求得快慢指针相遇节点 { meet = slow; while (meet != head)//两指针同时移动，相遇即是入口 { meet = meet->next; head = head->next; } return meet; } } return NULL; }
方法二实现代码
//求相交链表的交点的函数 struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { ListNode* pcurA = headA; ListNode* pcurB = headB; int countA = 0; int countB = 0; while (pcurA)//求出链表长度 { pcurA = pcurA->next; countA++; } while (pcurB) { pcurB = pcurB->next; countB++; } int tmp = abs(countA - countB);//长度差值 ListNode* slow, * fast; if (countA < countB) { slow = headA; fast = headB; } else { slow = headB; fast = headA; } while (tmp--)//长链表先走差值的步数 { fast = fast->next; } while (fast && slow)//同步比较 { if (fast == slow) return fast; fast = fast->next; slow = slow->next; } return NULL; } struct ListNode* detectCycle(struct ListNode* head) { ListNode* slow, * fast; slow = fast = head; ListNode* meet = NULL; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast)//先求得快慢指针相遇节点 { meet = slow; ListNode* newhead = meet->next; meet->next = NULL;//将环断开，变成两个相交的链表 return getIntersectionNode(head, newhead); } } return NULL; }
总结
两种方法可以自行选用
第一种方法属于推理复杂，代码简单第二种方法属于推理简单，代码实现细节复杂
可根据实际情况选择合适的方法
