题意

给定一个单链表，其中可能有环，现在要找出环的入口节点。

分析

方法一: 哈希表暴力
拿个哈希表记录一下走过的节点，第一个遇到的走过的节点就是环的入口。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head == NULL)return head;

        unordered_map<ListNode*, bool> map;

        ListNode* cur = head;

        while(cur->next != NULL){
            if(map[cur])return cur;
            map[cur] = true;
            cur = cur->next;
        }

        return NULL;
    }
};

方法二：快慢指针
链表中环有关的问题，可以考虑快慢指针。
快指针每次走两步，慢指针每次走一步，如果有环，一定会在环内相遇。
假设满指针在环内走了 c, 进入环之前的路长为 a, 环长为 b
f = a + nb + c, s = a + c
f = 2s
得到 : a + nb + c= 2a + 2c
a + c = nb
a = b - c + (n-1)b
而 b - c 就是当前慢指针离环入口的距离，因此如果慢指针走 a 步，那么它就会在环入口，问题是 a 未知，然而，起点到环入口也是 a 步，如果此时让一个新的指针从起点开始，每次走一步，每次慢指针也走一步，那么它们会在环入口相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head == NULL)return NULL;

        ListNode* fast = head, *slow = head;

        while(fast && slow){
            fast = fast->next;
            if(fast == NULL)return NULL;
            fast = fast->next;
            slow = slow->next;
            if(fast == slow)break;
        }
        if(fast == NULL)return NULL;
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }

        return fast;
    }
};