链表中环的入口节点

###参考环形链表

• 快慢指针扫描法--->判断是否有环(巧妙的做法)
• 两个指针first,second分别从起点开始走，first每次走一步，second每次走两步。如果过程中second走到***null***,则说明不存在环。
• 否则当first和second相遇后，让first返回起点，second呆在原地不动,然后连个指针每次分别走一步，当相遇时，相遇点就是环的入口。(理解这一步是找到环入口的关键)
  

以下是证明过程:

• a 是起点，b 是环的入口, c 是两个指针的第一次相遇点，a->b 所要经过的路程是x，b->c所要经过的路程是 y。
• 则当first走到 b 时，由于second比first多走一倍的路，所以second已经从 b 开始在环上走了 x 步,可能多余1圈。
• 假设 first 和 second 相遇点为 c 并且 c 距离 b 还差 y 步。所以 second 从 b 点走 y+x 步即可回到 b 点，所以 second 从 c 点开始走，走 x 步即可恰好走到 b 点，同时让first从头开始走，走 x 步也恰好可以走到 b 点，所以第二次相遇点就是 b 点，也就是环的入口.

参考代码

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return NULL; // C++ 中 NULL == nullptr == 0
        
        auto first = head, second = head;
        while (first && second){
            first = first->next;
            second=second->next;
            if(second) second = second->next;  // second 每次都比 first 多走一步
            else return 0;
            
            if (first == second){ // 相遇后,second 和 first 速度一样
                first = head;
                while (first != second){
                    first = first->next;
                    second=second->next;
                }
                return second;
            }
        }
        return nullptr;
    }
};