给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
思路：
两个指针，一快一慢，快指针一次走两步，慢指针一次走一步，如果有环，则两指针必会相遇。假设链表的头为head,入口点为enter,相遇点为meet。head到enter的距离为a，enter到meet的距离为b，meet到enter的距离为c。两指针相遇时，快指针走过的距离是慢指针的两倍，假设此时快指针绕了m圈，慢指针绕了n圈。则有等式a+b+m(b+c)=2(a+b+n(b+c)),由此等式可推出
m(b+c)=a+b+2n(b+c)
>> (m-2n)(b+c)=a+b
>> (m-2n)(b+c)-(b+c)+c = a
>> (m-2n-1)(b+c)+c = a所以一个从相遇点出发、一个从头节点出发的两个指针最终会在入口处相遇。
代码：
/**
* 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) {
if(head == nullptr) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
ListNode* cur = head;
while(cur != slow) {
cur = cur->next;
slow = slow->next;
}
return cur;
}
}
return nullptr;
}
};