题目：142. 环形链表||
难度：MEDIUM

算法思想

在第一节的时候，我们使用快慢指针解决了链表中存在环的问题。现在我们考虑怎么可以找到开始入环的第一个节点。

设慢指针走了k步，那么快指针走了2*k步。如果二者相遇，该坏上节点个数一定是k的公约数。

此时我们将慢指针调回头节点，下一次相遇的位置就是入点位置。

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast, *slow;fast = slow = head;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;if (fast == slow) break;}// 上面的代码类似 hasCycle 函数if (fast == nullptr || fast->next == nullptr) {// fast 遇到空指针说明没有环return nullptr;}// 重新指向头结点slow = head;// 快慢指针同步前进，相交点就是环起点while (slow != fast) {fast = fast->next;slow = slow->next;}return slow;}
};