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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr) {
            return nullptr;
        }
        ListNode *slow = pHead, *fast = pHead->next;
        int circleLen = 0, times = 1;
        // 1.查找相遇点
        while (slow != fast) {
            if (slow && fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            } else {
                return nullptr;
            }
        }
        // 2.存在环，则计算环长度
        while (times < 2) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                times++;
            }
            circleLen++;
        }
        // 3.slow从起点出发，fast从circleLen出发，相遇之处即为所求（环入口点）
        slow = pHead;
        fast = pHead;
        while (circleLen--) {
            fast = fast->next;
        }
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};