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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (!pHead || !pHead->next) return nullptr;
        ListNode *slow = pHead->next;
        ListNode *fast = pHead->next->next;
        while (fast && fast->next && fast != slow) {
            fast = fast->next->next;
            slow = slow->next;
        }
        if (!(fast && fast->next)) {
            return nullptr;
        }
        slow = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

思路：先找是否有环。找到后fast在相遇位置，slow回退到pHead，然后两个指针相同速度遍历，相遇时即为环起点。后面的思路可能需要图，感觉手撕的话一般不会要求列等式计算。

设pHead到环起点距离为m，环起点到相遇点为k，环长度为n。相遇前慢节点在环里转了a圈，快节点转了b圈。

因为fast走过的路程是slow的两倍，有2 * (m + a * n + k) = m + b * n + k，化简得m = (b - 2 * a) * n - k。

慢节点从pHead继续出发，到环起始点距离为m；快节点以相同速度走m = (b - 2 * a) * n - k，再加上快节点原本距离环起始点为k，总共离环起始点的距离为(b - 2 * a) * n，即也在环起始点。