蓝桥与力扣刷题（141 环形链表）

题目：给你一个链表的头节点 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
解释：链表中没有环。

第一种解题思路＋代码：（快慢指针）

代码：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {/**思路：1.判断链表是否为空或者单链表，是直接返回false2.声明快慢指针，遍历链表（快指针速度为一次两步，慢指针速度为一次一步）3.当快慢指针相遇时，可以判断出该链表存在环4.此时需要将一个指针重新指向链表的头节点5.快慢指针同时移动，每次各移动一步，终会在环的入口处相遇*/if(head == null || head.next == null){return false;}ListNode slowNode = head;ListNode fastNode = head;//遍历链表（快指针速度为一次两步，慢指针速度为一次一步）while(fastNode != null && fastNode.next != null){slowNode = slowNode.next;fastNode = fastNode.next.next;//快慢指针相遇时，该链表存在环if(slowNode == fastNode){//将一个指针重新指向链表的头节点slowNode = head;while(slowNode != fastNode){//快慢指针同时移动，每次各移动一步（是在判断链表存在环之后的快慢指针）slowNode = slowNode.next;fastNode = fastNode.next;}return true;}}return false;}
}

这道题在我解答之后去看了官网和一些大佬的题解，有对快慢指针来判断是否为环形链表相应的图解（作者：Caddy  题解：https://leetcode.cn/problems/linked-list-cycle/solutions/691164/yuan-lai-hui-luo-ji-qing-xi-jian-dan-yi-7o8tx/）

举例一
小汽车和自行车从跑道的起点同时出发
如果没有环道，那么小汽车永远离自行车而去
如果有环道，最终小汽车最终会追上自行车
举例二
大家初高中时候，学校操场的环形跑道上举行万米长跑，跑的快的学生经常会追上跑的慢的学生，也就是跑的快的学生第一次追上跑的慢的学生的时候，实际跑的快的学生比跑的慢的学生多跑了一圈。

第二种解题思路＋代码：（哈希表）引用力扣（作者：数据结构和算法  题解：https://leetcode.cn/problems/linked-list-cycle/solutions/438358/3chong-jie-jue-fang-shi-liang-chong-ji-bai-liao-10/）在该篇题解中，作者编写多种方法来解答环形链表，除了快慢指针和哈希表，还有反转链表和链表节点逐个删除的方法，对我而言大佬的多种解法帮我扩充了知识面（大家有兴趣也可以去搜索）。

代码：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//链表中存在环，那么在遍历链表的过程中，某个节点会重复出现。通过将每个节点添加到哈希集合中，如果某个节点已经存在于集合中，说明链表存在环。Set<ListNode> set = new HashSet<>();while (head != null) {//如果重复出现说明有环if (set.contains(head))return true;//否则就把当前节点加入到集合中set.add(head);head = head.next;}return false;}
}

总结：解答该题所用的快慢指针法只要存在速度差，在移动n次后快慢指针也终会相遇。因此，快慢指针的速度不限定是在2倍之差。另外，在写这道题时，我也苦恼了很久，在使用快慢指针遍历链表确实能够判断出该链表是否存在环，但是如何确定链尾连接到链表中的位置，并返回相应的下标？后面我查询AI时，AI给出了相应的解释：假设链表的起点到环的入口的距离为 x，环的长度为 y。当快慢指针第一次相遇时，慢指针走了 x+y 的距离，而快指针走了 x+2y 的距离（因为快指针比慢指针多走了一圈）。当我们将一个指针重新指向链表的头节点，并让两个指针同时移动时，它们会在环的入口相遇。这是因为：从链表起点到环的入口的距离是 x。从相遇点到环的入口的距离也是 x（因为快指针在环中多走了一圈，所以它在环中走的距离是 y，而从相遇点到环的入口的距离正好是 x）。