142. Linked List Cycle II
C++，链表，数学题。
链表的操作我们就不说了，这道题其实是一道数学题。
解法如下：
- 首先分别定义两个指针，一个一次走两步，一个走一步，分别为fast，slow，记录下快指针经过的结点数（不包括头结点）为lf，慢指针为ls，必有
lf = 2ls； - 假设有环链表的长度为l，环的长度为c，从头结点到环入口的距离为a；
- 一个走得快，一个走得慢，且路程中有环，则必定会相遇，且
lf - ls = c，设相遇时的点距离环入口为x； - 根据以上变量定义和关系，我们可以得出下列等式：
- 头结点到环入口的距离+环的长度-1=链表长，这个大家画图就明白了，即
l = a + c - 1 (1)； - 快指针走过的距离=链表长+1+相遇点到环入口的距离，画图就知道了，即
lf = l + 1 + x (2)； - 慢指针走过的距离=头结点到环入口的距离+相遇点到环入口的距离，这个显然，即
ls = a + x (3)； - 结合式(2)，式(3)，且
lf = 2ls，所以l = 2a + x - 1 (4)； - 联立式(4)和式(1)，得到
a = c - x (5)
- 头结点到环入口的距离+环的长度-1=链表长，这个大家画图就明白了，即
- 式(5)用人话说就是，头结点到到环入口的距离 = 环长 - 相遇点到环入口的距离；
- 也就是让慢指针从头结点开始走，让快指针从相遇点开始走，都是一次走一步，下次相遇点就是环入口。。。
解决了数学问题，写代码就很简单了，上述思路也包含了如何判断链表有环。。。 评论区有个更骚的操作，一次遍历就行了，利用了堆上内存必定由大到小的特点。即第二次到达环入口结点时，其地址一定比前一个结点小。。。
代码如下：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (slow) {
slow = slow->next;
fast = fast->next;
if (!fast) return nullptr;
fast = fast->next;
if (!fast) return nullptr;
if (fast == slow) break;
}
if (!slow) return nullptr;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
