题目描述：给一个链表，判断其中环的起始结点，若没有环则返回null。要求不改变链表，空间复杂度O(1)。
分析：这题与141题是同一个算法引出的一系列问题，即Floyd判圈算法，又称龟兔赛跑算法，可以在有限状态机、迭代函数或者链表上判断是否存在环，并求出该环的起点与长度的算法。
算法的核心思想是设置快慢指针，例如设fast指针的速度是slow指针的2倍，若两指针能相遇则说明有环，否则无环。
例如有环链表如下图：
算法可以解决的问题有：
- 判断链表中是否有环，即141题。
若就是一个循环链表，即Y点与X点是同一点，链表的尾结点链到头结点，此时由于fast指针速度是slow指针的2倍，故起点就是两者相遇点，每当slow指针回到起点则相遇，因为slow指针每走一圈即fast指针正好走两圈。
若是像上图的一般情况，则当slow指针到达Y处时fast指针已经绕圈走了一段距离，故不一定会在Y处相遇。列方程可得这是一个只与时间有关的方程，即过一段时间一定可以相遇。
若两指针在fast走到末尾还未相遇，则说明无环。
- 计算环的长度。
第一种方法：第一次相遇后，让slow继续走，记录到下次遇到fast时，即到达Z点时，slow走过的结点数。此时slow走了一圈，正好还在Z点相遇。
第二种方法：设环的长度为L，第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，得到a=c。发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，走过的结点数就等于环的长度。
找到环中第一个节点，即Y点。
根据结论a=c，让两个指针分别从X和Z开始走，每次走一步，则正好会在Y相遇，也就是环的第一个节点。将有环的链表变成单链表（解除环）
在上一个问题的最后，将c段中Y点之前的结点与Y的链接切断即可。判断两个单链表是否有交点，并找到第一个相交的结点。
先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，则判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。
分别计算两个链表的长度len1，len2，假设链表1较长，首先对较长的链表遍历len1 - len2个结点到结点p，此时结点p与链表2头结点到两者相交的结点的距离相同，在此时同时遍历两个链表，直到相遇的结点为止，这个结点就是相交的结点。
在slow指针入环后，在最多走一圈的时间内必将遇到fast，时间复杂度O(n)，空间O(1)。
代码：
/**
* 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 *slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast) //找到相遇点
{
ListNode *p = head;
while( p != slow) //slow从Z点出发，新指针P从起点X出发同时走，直到相遇
{
p = p->next;
slow = slow->next;
}
return p;
}
}
return nullptr;
}
};
