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

    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

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

    进阶：

    你是否可以使用 O(1) 空间解决此题？

    示例 1：

    输入：head = [3,2,0,-4], pos = 1
    输出：返回索引为 1 的链表节点
    解释：链表中有一个环，其尾部连接到第二个节点。
    示例 2：

    输入：head = [1,2], pos = 0
    输出：返回索引为 0 的链表节点
    解释：链表中有一个环，其尾部连接到第一个节点。
    示例 3：

    输入：head = [1], pos = -1
    输出：返回 null
    解释：链表中没有环。

    思路：
    方法一：哈希表
    思路与算法
    一个非常直观的思路是：我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。
    复杂度分析

    时间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。

    空间复杂度：O(N)O(N)，其中 NN 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

    方法二：快慢指针
    参考资料：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

    1. /**
    2.  * Definition for a singly-linked list.
    3.  * class ListNode {
    4.  *     public $val = 0;
    5.  *     public $next = null;
    6.  *     function __construct($val) { $this->val = $val; }
    7.  * }
    8.  */
    10. class Solution {
    12.     function detectCycle($head){
    13.         $fast = $slow = $head;
    14.         while($fast != null && $fast->next !== null){
    15.             $fast = $fast->next->next;
    16.             $slow = $slow->next;
    17.             if($fast == $slow){
    18.                 $m = $head;
    19.                 $n = $slow;
    20.                 while($m != $n){
    21.                     $m = $m->next;
    22.                     $n = $n->next;
    23.                 }
    24.                 return $m;
    25.             }
    26.         }
    27.         return null;
    28.     }
    29. }

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。