题目描述

给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出$null$。

数据范围

节点 $val$ 值取值范围 $[1,1000]$。
链表长度 $[0,500]$。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

虽然这道题的正解是快慢指针，但是最简单的做法还得是$map$。
我们可以记录每个数出现的次数，如果出现了超过$1$次，就说明有环，直接输出这个数就行了。

/**
 * 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) {
        //申请一个mapp
        map <int, int> mapp;
        //如果是空的，就直接返回NULL，否则SF会给你整蒙了
        if (head == NULL) return NULL;
        auto q = head;
        while (q -> next)
        {
            //把当前这个数对应的mapp加一
            q = q -> next;
            mapp[q -> val] ++;
            //如果出现了超过1次，直接返回这个点的指针
            if (mapp[q -> val] > 1)
                return q;
        }
        return NULL;
    }
};

好了，这篇题解到这里就结束了。感谢观看！Thanks♪(･ω･)ﾉ！！！
$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$