题目描述：

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

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

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

示例 1：

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

环形链表Ⅱ - 图1
示例 2：

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

环形链表Ⅱ - 图2
示例 3：

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

环形链表Ⅱ - 图3
进阶：
你是否可以不用额外空间解决此题？

算法实现：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  9. /**
  10.  * @param {ListNode} head
  11.  * @return {ListNode}
  12.  */
  13. var detectCycle = function(head) {
  14.     if (head === null || head.next === null) return null
  15.     var slow = head
  16.     var fast = head
  17.     while (true) {
  18.             if (fast === null || fast.next === null) return null
  19.             fast = fast.next.next
  20.             slow = slow.next
  21.             if (fast === slow) break
  22.     }
  23.     fast = head;
  24.     while (slow !== fast) {
  25.         slow = slow.next
  26.         fast = fast.next
  27.     }
  28.     return fast
  29. };

思考：

与上一题不同之处在于要计算出环的入口，引用了别人的思路。思路如下：
**构建双指针第一次相遇：

设两指针 fast，slow 指向链表头部 head，fast 每轮走 22 步，slow 每轮走 11 步；
若 fast 指针走过链表末端，说明链表无环，直接返回 null（因为每走 11 轮，fast 与 slow 的间距 +1+1，若有环，快慢两指针终会相遇）；
当 fast == slow 时，代表两指针在环中 第一次相遇，此时执行 breakbreak 跳出迭代；
第一次相遇时步数分析： 设链表头部到环需要走 aa 步，链表环走一圈需要 bb 步，则链表共有 a+ba+b 个节点；设两指针分别走了 ff， ss 步，则有：
快指针走了慢指针 22 倍的路程，即 f = 2sf=2s；（fast 每轮走 22 步，slow 每轮走 11 步）
快指针比慢指针多走了 nn 个环的长度，即 f = s + nbf=s+nb；（双指针都走过 aa 步，直到相遇 fast 比 slow 多走整数倍环的长度）
代入可推出：f = 2nbf=2nb，s = nbs=nb，即快慢指针分别走了 2n2n，nn 个环的周长。
构建双指针第二次相遇：

将 fast 指针重新指向链表头部 head，slow 指针位置不变，此时 fast走了 00 步，slow 指针走了 nbnb 步；
令双指针一起向前走，两指针每轮都走 11 步；
当 fast 指针走到 aa 步时，slow 指针正好走到 a + nba+nb 步，此时 两指针重合并同时指向链表环入口 。
最终返回 fast 或 slow 即可。

总结：

进一步熟悉了双指针法的运用。