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

哈希

遍历链表，用map记录链表中每个结点出现的次数，第一次重复出现的结点就是入口节点。

C++代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_map<ListNode *, int> mp;
        while (pHead) {
            if (mp[pHead]) {
                return pHead;
            }
            mp[pHead]++;
            pHead = pHead->next;
        }
        return NULL;
    }
};

时间复杂度：O(n) 空间复杂度：O(n)

快慢指针

设置两个指针，快指针每次走两步，慢指针每次走一步，若链表有环，两指针一定会在环中相遇，如下图：

设链表起点到入口的距离为a，入口到相遇点距离为b，相遇点到入口的距离为c,因为快指针比慢指针走得快，当慢指针进入环里时，可以看成快指针在环里追赶慢指针，当两者相遇时，快指针至少在环里走过一个完整的圈，否则就说明两个指针速度相等，与假设不符。所以当两指针第一次相遇时，快指针走过的距离rd = a + k(b + c) + b。慢指针走过的距离ld = a + b。因为快指针走过的距离是慢指针的二倍，所以a + k(b + c) + b = 2(a + b)，即a = c + (k - 1)(b + c)。这个式子说明，当两指针相遇时，我们把其中一个指针放到起点，另一个指针位置不变，两个指针每次都走一步，他们最终会在起点相遇。留在环里的指针第一次到达入口后，可能会再走(k - 1)圈。

C++代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode *fast = pHead, *low = pHead;
        while (fast && fast->next) {
            low = low->next;
            fast = fast->next->next;
            if (fast == low) {break;}
        }
        if (!fast || !fast->next) {return NULL;}
        fast = pHead;
        while (fast != low) {
            fast = fast->next;
            low = low->next;
        }
        return fast;
    }
};

时间复杂度：O(n) 空间复杂度：O(1)