LeetCode-142 环形链表II

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

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

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

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。对应代码中返回入环的节点对象即可。

题解
分析
题目是得到环形链表的环入口位置，那么很自然的，我们思路就会是: 先判断链表中是否包含环，若不包含环可以直接返回null 了。若包含环，这时才就需要通过某种方式去找到环的入口位置。

• 判断链表中是否包含环:

  对于链表中是否包含环的判断在链表的处理中算是很经典的问题了，一般的，我们用快慢指针来做判断，快慢指针若能在遍历链表时在某个节点相遇，就认为链表中存在环，否则若快指针走到了链表的末尾(null) 则说明链表中不存在环。
  下面看看为什么存在环时，快慢指针一定能相遇。 这里快慢指针的定义如下:
  慢指针: 在遍历链表时一次只向前走一个元素
  快指针: 在遍历链表时一次向前走两个元素

  都从头节点开始走，快指针毋庸置疑是走在前面的那个指针，若链表中不存在环，它肯定也是率先走到链表末尾的那个指针(率先为null)；若链表中存在环，快指针一次向前移动两个位置速度可视为2，类似的，慢指针的速度就为1，当慢指针也浸入环内时，这时两个指针在环内移动可以看成快指针追逐慢指针的过程，他们的速度差为2-1 = 1， 因此快指针每走一次就缩小与慢指针的一个距离。 以此类推，快指针一定会在某个节点与慢指针相遇。

  因此环的判断可以能否在fast 走到null前相遇来判断

• 找出环的入口位置

  如果存在环，那么环的入口位置怎么确定？ 这里我们可以对环形链表快慢指针的移动做一个量化分析。 假定
  头结点到环入口的节点的距离为 a , 快慢指针在环中相遇节点距离环的入口的位置为 c ,环的长度为L 。根据快慢指针相遇前走过的距离有:
  
  其中 n 为快指针绕环转过的圈书，另外上述公式还隐含了一个条件: 慢指针在进入环之后不用绕环走一圈就能与快指针相遇。 这里也可以这么理解: 慢指针在进入环之后快指针离慢指针最远的距离就是在慢指针前面一个节点，那么这种情况下快慢指针在什么位置相遇呢？ 可以通过计算获得，距离为L-1, 快指针需要走 L-1 步就能赶上慢指针，而慢指针在这时也才走了L-1步达到环入口的上一个位置，因此慢指针并没有来得及绕环一圈。

由上述移动距离公式可得 ：

a = nL - c 能说明啥？ 从下图中可以看出， 若从相遇位置的节点继续向前走 nL - c 步走到的位置就是环的入口位置。如果是这样我们只需要再安排两个指针一个从链表的头结点开始，另一个从快慢指针相遇的位置开始，那么他们一定可以在环的入口位置相遇，这时相遇的这个节点就是环的入口节点。

实现

 if(null == head || head.next == null) return null;
        ListNode fast = head, slow = fast;
        // 判断链表是否含环,不含环则返回null
        do{
            slow = slow.next;
            if(fast != null && fast.next != null){
                fast = fast.next.next;
            }else{
                break;
            }
        }while(fast != slow);
        if(fast == null || fast.next == null) return null;
        // 若含环，找出环的入口
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;