原题目链接142.环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例如下：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
ListNode节点结构如下：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
解法1：哈希表
思路
遍历时记录每一个被遍历过的节点，并遍历过程中判断当前节点是否已被存储过。
若链表无环。则最终遍历会顺利结束，遍历过程中没有节点被重复向容器中添加。若链表有环。则在遍历时，会出现节点将要被重复记录的情况，遍历过程中第一被发现已经被记录过的节点就是环的入口节点。 复杂度
时间复杂度：O(n)，n为链表中的节点数，时间复杂度同一次链表的遍历。空间复杂度：O(n)，n为链表中的节点数，需要额外存储链表的每个节点。 AC代码
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet hashSet = new HashSet<>();
while(head != null){
if(hashSet.contains(head)){
return head;
}
hashSet.add(head);
head = head.next;
}
return null;
}
}
解法2：快慢指针
思路
思路分为两个部分
判断成环设定两个指针来遍历整个链表，指针移动速度一快一慢，快指针的移动速度是慢指针的两倍
若链表无环。则遍历速度快的指针会成功遍历。若链表有环。在环路中，快慢指针同时移动，最终快指针一定会追上慢指针，当快慢指针的指向相等时，则表示链表有环。 寻找成环入口
先将链表划分为三个区域，如下图所示，a代表环外部分距离，b代表环入口到相遇点距离，c代表相遇点到环入口的距离，再设快指针fast已经在环内走了n圈。
由上列假设可以推导出快慢指针走过的距离
slow = a + bfast = a +n*(b + c) + b
又因为fast移动速度是slow的两倍，所以 fast = 2 * slow，继而可以推导出
a = c + (n - 1)(b + c)
由上式可以发现，从相遇点到环入口的距离于从链表起始点到环入口的距离相等，此时只需要让一个指针指向链表头节点，与相遇点的任一指针等速移动，当二者相遇时，相遇点就是环入口。
复杂度时间复杂度：O(n)，n为链表中节点数目，两部分移动——判断成环和判断环位置，指针的移动都不会超过链表长度，因此时间复杂度为O(n)。空间复杂度：O(1)，只需要额外的几个指针。 AC代码
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
ListNode slow = head;
ListNode fast = head;
while(true){
fast = fast.next;
if(fast == null) return null;
fast = fast.next;
slow = slow.next;
if(fast == null) return null;
if(slow == fast) break;
}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
