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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //     unordered_set<ListNode *> st;
        //     while (pHead)
        //     {
        //         if (st.count(pHead))
        //         {
        //             return pHead; // 若已经记录过，直接返回
        //         }
        //         st.insert(pHead); // 记录当前结点
        //         pHead = pHead->next;
        //     }
        //     return nullptr; // 无环
        ListNode *fast = pHead, *slow = pHead; // 快慢指针都指向头节点
        // 循环快指针是否为空
        while (fast)
        {
            // 慢指针走一步
            slow = slow->next;
            // 如果快指针为空了，直接返回null  说明无环
            if (fast->next == NULL)
            {
                return NULL;
            }

            // 否则快指针走两步
            fast = fast->next->next;
            // 如果两个指针相交，此时慢指针已经走了nb步
            if (fast == slow)
            {
                //    快指针重新指向头节点，再遍历一次（这次是要每次走一步即可），
            // 直到两个指针相遇为止，然后返回快指针节点即可
              fast = pHead;
              while (fast != slow)
              {
                fast = fast->next;
                slow = slow->next;
              }
              return fast; // 找到入口节点，直接返回
            }
        }
        return NULL;
    }
};