1、题干

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

2、解题

前提给定：（链表节点的定义和链表的形成）

链表节点定义如下：

public class ListNode {int val;          // 节点的值ListNode next;    // 下一个节点ListNode(int x) {val = x;next = null;}
}

构建链表的方式示例：（如上示例1，[3,2,0,-4]的链表构建过程）

public static void main(String[] args) {// 创建节点ListNode head = new ListNode(3); // 3ListNode node2 = new ListNode(2); // 2ListNode node3 = new ListNode(0); // 0ListNode node4 = new ListNode(-4); // -4// 构建链表顺序和环head.next = node2;node2.next = node3;node3.next = node4;node4.next = node2;   // 环：-4 → 2System.out.println(hasCycle(head));}

方法一：（哈希映射法）

可以遍历链表数据，依次将元素全部添加到Hash结构中（如：HashSet），当Set集合中已经存在，说明进行了2次添加，即存在环。

代码示例：

public static boolean hasCycle(ListNode head) {Set<ListNode> hasSet = new HashSet<>();while (head!=null){// 方法1，通过set的包含方法校验
//            boolean contains = hasSet.contains(head);
//            if (contains){
//                // set中已经包含，二次添加，说明有环，退出循环
//                return true;
//            } else {
//                hasSet.add(head);
//            }// 方法2，通过add方法校验，add添加失败，说明节点已存在，即有环boolean addFlag = hasSet.add(head);if (!addFlag){// 没有添加成功，说明已存在，直接结束return true;}head = head.next;   // 链表向下遍历}return false;}

方法二：（快慢指针法）

定义两个指针，分别指向当前节点（慢指针）和当前节点的下一个节点（快节点）。
慢指针每次向后移动1步，快指针每次向后移动2步。
如果不存在环，那么快指针必定会优先走到链表末尾null的位置。
如果存在环，那么当快指针和慢指针都进入环后，每次增长后，两者的距离都会缩进1步，直到相遇。

代码示例：

private static boolean hasCycle(ListNode head) {if (head == null || head.next == null) {// 当前为空或指向为空，不存在环return false;}ListNode slow = head;    // 慢指针ListNode fast = head.next;   // 快指针// 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一,直到slow和fast走到同一个位置。此时刚好多经历了一个环的长度Nwhile (slow != fast) {// 当链表中不存在环时，快指针将先于慢指针到达链表尾部。if (fast == null || fast.next == null) {return false;}slow = slow.next;        // 慢指针走1步fast = fast.next.next;   // 快指针走2步}// 跳出循环，说明存在环return true;}

向阳出发，Dare To Be！！！