一.题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
二.题目解析
public ListNode detectCycle(ListNode head) {
/*一次遍历，修改遍历过的节点值为Integer.MIN_VALUE，若还将遍历到这个值，证明有环
时间复杂度O(n),空间复杂度O(1),缺点：修改了链表
* */
int min = Integer.MIN_VALUE;
ListNode cur = head;
while (cur != null){
//这个标记再次出现，意味这个结点被访问过，说明链表循环
if(cur.val == min){
return cur;
}
//给此正在遍历的节点赋值
cur.val = min;
//遍历下一节点
cur = cur.next;
}
return null;
}
2.
public ListNode detectCycle1(ListNode head) {
/*hashset保存遍历过的节点
时间复杂度O(n),空间复杂度O(n)
* */
HashSet<ListNode> listSet = new HashSet<>();
ListNode p = head;
while(true) {
if(p == null) {
return null;
}
if(listSet.contains(p)) {
return p;
}
listSet.add(p);
p = p.next;
}
}
3.
假设第一次相遇时，x是头结点到环起点的距离，y是环起始点到环相遇点的距离，z是环相遇点到环起始点的距离。（y+z则表示一圈）
注：因为fast速度是slow的两倍，相遇的时候所用时间相同，所以走过的路程也是二倍关系
参考来源：
https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/xiang-xi-tu-jie-ken-ding-kan-de-ming-bai-by-xixili/
public ListNode detectCycle2(ListNode head) {
/*快慢指针法,当快慢指针速度差为1的时候，必会在环内相遇。
当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，
同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会和慢指针相遇
时间复杂度O(n),空间复杂度O(1)
* */
ListNode fast = head,slow = head;
while (fast != null && fast.next != null){
//快慢指针按照不同的速度移动
fast = fast.next.next;
slow = slow.next;
//此时在环内相遇
if(fast == slow){
fast = head;
//fast走过x距离，slow从相遇点走过z距离（或者若干圈回到相遇点+z距离），即可同步到达环入口
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
