难度：中等
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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 解释：链表中没有环。
进阶： 你是否可以不用额外空间解决此题？
分析：
首先fast走2步，slow走1步，如果有环，必然能相遇；
然后就是找入口；
设到入口之前的长度为a，环长度为b；总长度就是a+b；
设快指针走了fast步，慢指针走了slow步；fast = 2 * slow；①
当快慢指针重合的时候，fast - a = slow - a + nb；除掉都走了的a的长度，快慢指针在同一个地方，
说明快指针比慢指针多走了n圈，fast = slow + nb；②
①②结合可知，slow = nb；
从开头开始走的话，走a+nb的距离后，会停在入口；现在slow=nb，只要再走a步就能到入口；
此时让快指针回到head，快慢指针都一步步走，相遇的时候，就会正好在入口处，因为快指针需要a步到入口，慢指针也是；
代码：
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head,fast = head; do{ if(fast==null || fast.next==null) return null; slow = slow.next; fast = fast.next.next; } while (slow != fast); fast = head; while (slow != fast){ slow = slow.next; fast = fast.next; } return fast; } }结果：
