给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

    说明：不允许修改给定的链表。

    示例 1：
    输入：head = [3,2,0,-4], pos = 1
    输出：tail connects to node index 1
    解释：链表中有一个环，其尾部连接到第二个节点。

    示例 2：
    输入：head = [1,2], pos = 0
    输出：tail connects to node index 0
    解释：链表中有一个环，其尾部连接到第一个节点。

    示例 3：
    输入：head = [1], pos = -1
    输出：no cycle
    解释：链表中没有环。

    进阶：
    你是否可以不用额外空间解决此题？

    方法1：哈希表，第一个被重复访问的结点就是入环的第一个结点。

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    11. class Solution {
    12. public:
    13.     bool hasCycle(ListNode * head)
    14.     {
    15.         unordered_set<ListNode *> seen;  // 记录某一个节点是否访问过
    16.         while(head)                      // 到达尾节点
    17.         {
    18.             if (seen.count(head))        // 如果访问过head节点
    19.                 return true;
    20.             seen.insert(head);           // 插入
    21.             head = head->next;
    22.         }
    23.         return false;
    24.     }
    25. };

    方法2：快慢指针
    环形链表II 【链表】【双指针】【哈希表】 - 图1
    原理图(侵权请联系删除)
    原理说明

    2*distance(p_slow) == distance(p_fast) 2 * (F + a) == F + a + b + a F == b

    step1: 如果存在环形，则找到汇合的点intersectNode
    step2: 分别从head与intersectNode出发，一直到交点就是进入环形的起点。
    环形链表II 【链表】【双指针】【哈希表】 - 图2
    示意图(侵权联系删除)
    环形链表II 【链表】【双指针】【哈希表】 - 图3
    示意图(侵权联系删除)

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    12.     // 方法1： 哈希表
    13.     ListNode *detectCycle(ListNode *head) {
    14.         unordered_set<ListNode *> seen;
    15.         ListNode * p_node = head;
    16.         while(p_node)
    17.         {
    18.             if (seen.count(p_node) != 0)
    19.                 return p_node;
    20.             seen.insert(p_node);
    21.             p_node = p_node->next;
    22.         }
    23.         return NULL;
    24.     }
    25. }
    class Solution {
public:
    // find intersect Node
    ListNode * getIntersectNode(ListNode * head)
    {
        ListNode * p_fast = head;
        ListNode * p_slow = head;
        while(p_fast != p_slow)
        {
            if (p_fast == nullptr || p_fast->next == nullptr)
                return NULL;
            p_fast = p_fast->next->next;
            p_slow = p_slow->next;
        }
        return p_fast;
    }

    // 方法2：快慢指针
    ListNode * detectCycle(ListNode * head)
    {
        if (head == nullptr || head->next == nullptr)
            return nullptr;
        ListNode * intersect = getIntersectNode(head);
        if (intersect == nullptr)
            return nullptr;
        ListNode * ptr1 = head;
        ListNode * ptr2 = intersect;
        while(ptr1 != ptr2)
        {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }
        return ptr1;
    }
}

    欢迎 交流，批评指正！