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

方便分析作图如下，假设a是链表头节点，b是链表中环的入口节点，c是快慢指针相遇的节点。

三段路径长度按顺时针分别称为ab，bc，cb。链表中环长度为s = bc + cb。

我们需要计算，在c点相遇的时候，快慢指针分别走了多远？利用快慢指针长度的两倍关系去求解问题。

快指针到c点走过的长度 s1 = ab + bc + n * s = ab + bc + n * (bc + cb)

快指针走的距离包括ab+bc的距离，再加上在圆环中环绕圈数的距离。

那么慢指针的长度如何计算？他在环中也走了多少圈？

这就需要理解一个概念：

从慢指针进入环时，到快慢指针相遇，慢指针走过的距离是一定小于等于环的大小。（如果整个链表是一个环，则慢指针走过距离等于环大小） 慢指针进入环后，可以看成快指针在后面追赶慢指针。

最好情况快指针就在b的左侧，移动一步两者便相遇。 最差情况为快指针在b的右侧，需要多绕不到一圈的距离。 分析最差情况：假设慢指针走了一整圈环，回到b点时快指针才追上，慢指针移动长度为s，快指针移动长度则为2s-1。但实际上快指针速度是慢指针两倍，即实际应走距离为2s。可以反证出在慢指针走完一圈之前，快指针必然追上慢指针。

理解了上述概念，可以很快得出，慢指针长度 s2 = ab + bc

已知了快指针是慢指针两倍，即 2 *(ab + bc) = ab + bc + n * (bc + cb)

推出：ab = (n-1) * (bc + cb) + cb

含义为：链表头到环入口的距离=相遇点到环入口的距离+（n-1）圈环长度

分析到这里，其实已经得出答案了。两个链表相遇后，一个指针指向相遇的位置，一个指针指到链表的头节点。两个指针均向后移动，判断当两者相同时，该节点便是链表到环的入口节点。

代码参考：

/*
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 != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                break;
            }
        }
        if(fast==nullptr || fast->next == nullptr) return nullptr;
        fast = pHead;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};