第一讲：链表中环的入口结点

题目：链表中环的入口结点
给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

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

样例

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

则输出环的入口节点3.

题目解析：
方法一：哈希表
我们可以使用unordered_set，来保存节点指针，如果发现有相同的指针（set的大小不变），则表示是入口节点

方法二：快慢指针
原理：快指针每次走两步，慢指针每次走一步，如果有环则一定会相遇
如图，假设慢指针从a走到b最后与快指针相遇于c，如果慢指针返回到b点，则快指针会返回到d点（因为会多走y步）
那么我们可以发现当慢指针走到b点，那么快指针就会走到d点（因为回退得出的），那么x+y就会是圈的整数倍（其实可能快指针已经在圈里走过很多圈了，但是这不影响，相当于取余操作）
最后我们将慢指针移到起点，两个指针走同样的步数，则就会在入口相遇（因为快指针已经走了y步，再走x步肯定会在b点，而慢指针走x步也会在b点）

执行次数：x+y+2x+2y+2x=5x+3y（因为x+y小于总长度，所以时间复杂度0（n））

/** * 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)return NULL;
        set<ListNode *> s;
        while(head->next)
        {
    
            int size=s.size();
            s.insert(head);
            if(size==s.size())return head;
            head=head->next;
        }
        return NULL;
    }
};