原链接：https://leetcode-cn.com/leetbook/read/leetcamp-2/aasa6m/

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

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

    不允许修改 链表。

    示例 1：
    image.png

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

    示例2：
    image.png

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

    示例3：
    image.png

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

    解法：
    先看边界分析，有两种情况：

    • 如果头节点为空，则直接返回head（空节点）；
    • 链表只有一个节点，则直接返回null。

    再看暴力解法（时间复杂度O(n)）：

    • 遍历所有节点；
    • 用一个对象记录所有访问过的节点；
    • 碰到第一个对象已经记录过的节点，返回该节点；
    • 如果遍历完仍然不存在已经记录过的节点，则返回null。

    暴力解法使用了额外的空间，不符合题目要求，那么换一种思路如下：

    • 是否存在环
    • 环的入口在哪里

    先解决第一个问题，是否存在环？答案：

    • 设置快慢指针，同时从起点出发，快指针每次走两步，慢指针每次走一步；
    • 若在任何时刻，快指针没有后一个节点，则无环；
    • 若在任何时刻，快慢指针重合，则有环。

    再解决第二个问题，环的入口在哪里？用数学的思维去解答
    image.png
    h-起点，s-环入口点，p-快慢指针碰撞点，h到s的距离-L，环上的总距离-Q，总共走了n轮环，求解s
    解：

    • 慢指针走了 n 轮到达 p 点，则有：n = L + Ds~p。
      • Ds~p 表示环上从 s 走到 p 的步数，则有Ds~p= Q - Dp~s。
      • 联立上两式，得出：n = L + Q - Dp~s。
    • 快慢指针相遇时，快指针行进总距离为 2n，快指针和慢指针形近距离刚好相差圈数的倍数(2n - n) % Q = 0。
    • 可推导出 n = x * Q，其中 x 为非负整数。
    • 代入上式得x * Q = L + Q - Dp~s，转化后得到L = Dp~s + (x - 1) * Q。

    最后一个等式意味着，用两个指针，分别从h和p开始走，直到他们相遇就是环的入口。

    tips：在所有变量值均未知的情况下，可以使用推导出的相等关系，利用环上碰撞的特殊性质达到目的。

    解题思路：

    • 定义两个指针 a 和 b，同时从起点 h 出发，a 每次走两格，b 每次走一格。
    • 如果未碰撞，则表示无环。
    • 如果碰撞，则标记碰撞点为 p。
    • a 从 h 出发，b 从 p 出发，速度均为1。

    • 最后 a 和 b 会碰撞，标记碰撞点为 s，返回 s 即可。

      /**
* Definition for singly-linked list.
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
  if(head===null)return null;
     if(head.next===null)return null;
     if(head.next.next===null)return null;

  var a = head.next;
  var b = head.next.next;

  while(a!==null && b!==null){
      if(a===b)break;
      a=a.next;
      b=b.next;
      if(b!==null)b=b.next;
  }

  if(a===null || b===null)return null;

  a=head;
  while (a!=b) {
      a=a.next;
      b=b.next;
  }
  return b;
};