题解 | #链表中环的入口结点#

快慢指针的解法关键在于，当快慢指针相遇时，该节点与入口节点的距离=起始节点到入口节点的距离：

起始节点到入口节点距离为a，环上节点为b，快指针走了f步，慢指针走了s步，于是当他俩相遇时：

1）f = 2s

2）相遇节点与入口节点的顺时针距离为a

能得出第二个结论是由于：

当慢指针走到入口时，快指针必定走了2a步，即在环内已经走了a步（若a>=b，则走了至少1圈；若a<b，则尚未走满一圈）。

此时快指针与慢指针距离为a步，还需要相对多走b-a步快指针才能套圈遇到慢指针，又由于相对速度是倍数关系，因此慢指针还需要走b-a步。当然特殊情况下b=a，此时已经相遇。

所以，以顺时针为例：入口节点->相遇节点距离=b-a，相遇节点->入口节点距离=a，只需要分别从相遇节点和起始节点同步走a步即可在入口相遇。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(!pHead) return NULL;
        
        ListNode *p1, *p2;
        int cnt = 0;
        p1 = pHead;
        p2 = pHead;
        while(p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1 == p2) break;
        }
        if(!p2 || !p2->next) return NULL;
        p2 = pHead;
        while(p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p2;
    }
};