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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* head) {
        // 思路：先看是否成环，若不成环，则直接返回空
        // 成环，则找相遇节点
        // 找到后，分两指针，指向起点和相遇点
        // 同时前进，当两节点指向一致时，即为入口节点
        // 推导：慢指针走到相遇节点要走x + y
        // 快指针走到相遇节点要走x + y + n * (y + z)
        // 而快指针所走步数是慢指针两倍，故2(x + y) = x + y + n * (y + z)
        // 消除，并化简，得x = (n - 1)(y + z) + z
        // 当n为1时，x = z
        ListNode* slow = head, * fast = head;
        while (fast != NULL && fast->next != NULL) { // fast->next也需判断是否为空，否则fast->next->next有可能会访问空节点而报错
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1; 
            }
        }
        return NULL;
    }
};