给定单链表，判断是否有环，如果有返回环入口

这是一题常见的面试题，考察求职者对链表的理解，题目在leetcode上：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
首先来判断链表有没有环。看一个直观的例子：假设小明和专业运动员在400米标准环形操场上比赛跑步，由于长久缺乏锻炼，小明匀速跑一圈需要2分钟，而运动员匀速跑一圈只要1分钟。那么如果两个人同时、同一点出发，1分钟后小明跑了半圈，而运动员已经跑完一圈，开始第二圈；2分钟时，小明终于跑完一圈，而运动员刚好跑完第二圈，整整比小明多跑一圈，两人在终点相遇。如果运动员在小明前方S米处和小明同时出发，那么运动员会在小明跑完一圈前就追上小明（可怜的小明）。

回归问题，如果我们设定两个指针p1、p2，开始时指在链表头head，p1代表小明，每次前进一步；p2代表运动员，每次前进两步。如下图环形链表中，6步之后p2追上p1，再次相遇。

环链表

对于一般链表，p1、p2仍然同时从表头A点出发，由于前面有段非环的直线路程，当p1到B点进入环的时刻，p2已经在环内跑了一段路了，此刻开始，类似运动员和小明同时出发，而运动员的出发点领先于小明，在不超过一圈的路程内，运动员能够追上小明，p2也能在一圈以内赶上p1，假设两指针在C点相遇，此时，p1==p2，利用这个条件，我们可以断定链表有环。否则，当运动员跑到了尽头，还没有和小明相遇，说明他们的跑道没有环。

一般链表

再来看看环的入口在哪里。我们利用p1、p2在C点相遇的时刻来分析，假设AB的距离为s，BC的距离为r，CB的距离为l，p1走过距离为a = s + r则可以有以下关系：

(1)总长度 = s + r + l;
(2)环的长度 = r + l;
(3)p2走过距离 = 2a;
(4)p2 - p1 = a = s + r;
相遇时，p2比p1在环内多走了n圈(n>=1): 
(5) p2 - p1 = n(r + l)；
结合(4)、(5): n(r + l) = s + r;
nr - r = s - nl;
(n - 1)r = s - (n - 1)l -l;
(6) (n -1)(r + l) = s - l;

从（6）我们可以看出一些规律（注意：环的长度 = r + l），当n = 1时，说明p2比p1多跑了一圈，此时，s = l。当n > 1时，说明p2比p1多跑了整整(n -1)圈再相遇，考虑s - l为环长度的(n -1)倍，(n -1)(r + l) + l = s，说明如果一个节点从A点开始，走s的距离和从C点开始走(n -1)圈再多l的距离刚好又能相遇在B点，B也正是环的入口。
分析完毕，再上C++代码：

 struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
 };
ListNode *detectCycle(ListNode *head) {
        ListNode *p1 = head, *p2 = head;
        bool hasCycle = false;
        // 特殊情况判断
        if(head == NULL)
            return NULL;
        // p2走得快，当p2->next == NULL时，说明没有环
        while(p2 && p2->next)
        {
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1 == p2) 
            {
               //  有环，立下flag
                hasCycle = true;
                break;
            }
        }
        if(!hasCycle)
        {
            return NULL;
        }
       // 一个从A前进，一个从C前进
        p2 = head;
        while(p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }