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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;

        while(fast->next && fast->next->next) {
            fast = fast->next->next;
            slow = slow->next;

            // 链表存在环.
            if (fast == slow) {
                fast = pHead;
                while (fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }

        return nullptr;
    }
};

假设头结点到入口处的节点数为 a，环中节点数量为 b，到入口处需要走的节点数为r

快指针所走节点数为 f，慢指针所走节点数为 s

快慢指针相遇时，快指针所走节点数为 f = s + nb，又 f = 2s，此时两个指针所走节点数分别为：

• 快指针：f = 2nb
• 慢指针：s = nb

又 r = a + nb，所以只要让 r 再走 a 步就可以走到入口处，s表达式中的n和r表达式中的n无所谓是相同或者不同的，因为无论绕几圈都是停留在环中同一个节点处

参考力扣 142. 环形链表 II K神题解

****