找出有环链表中环的入口节点

今天去面试碰到这个问题，因为之前见过思路大概知道，就是忘了怎么证明，然后就在那里想啊想啊，结果还是没想出来。然而一回宿舍马上又想出来了，哎。

求法：两个指针p和q，每次p走一步，q走两步，最后它们将在环上的某一个节点相遇，这时再弄一个指针r从链表表头开始，然后r走一步，p也走一步，那么最后当r==p的时候指向的节点就是环的入口节点。

证明：

假设p，q在S相遇，此时有：

p走过的节点数：L+a

q走过的节点数：L+a+n（a+b）

因为q走的节点数是p的两倍，因此得出一条等式：2L+2a=L+a+n（a+b）,化简为：L=（n-1）（a+b）+b。

这条等式说明：r指针走完L个节点到达环入口，p走过的节点数为n-1个圆和b个节点，那么这时p也刚好在环入口，逆推过来就是r==p时r和p一定都同时指向环入口节点（可以证明不可能都指向其它同一个节点）。

代码：

/**
 * 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 == NULL || head->next == NULL) {
            return NULL;
        }
        ListNode* p = head;
        ListNode* q = head;
        p = p->next;
        q = q->next->next;
        while(q != NULL && q->next != NULL && p != q) {
            p = p->next;
            q = q->next->next;
        }
        //没环
        if(p != q) {
            return NULL;
        }

        ListNode* r = head;
        while(r != p) {
            r = r->next;
            p = p->next;
        }
        return r;
    }
};