Suffering, for the weak is the tomb of death, and for the strong is the soil of germinal ambition.​

1. 题目描述

2.  题目分析与解析

2.1 思路一

这个题目就是判断一个链表有没有环，其实我们之讲过一个题目，就实现了判断链表有没有环的步骤：面试经典150题——快乐数，并且还有图示，就是使用快慢指针法，因此在本篇文章中就不过多赘述了，直接给出代码思路。

代码思路：

1. 定义两个指针，分别表示快慢指针

2. 让快指针以2的速度前进，慢指针以1的速度前进

3. 如果两个指针相交，说明链表中存在环结构，返回true

4. 如果遍历到结尾仍然没有返回false就说明没有环，返回false

2.2 思路二

因为我们用一种很简单的思路如何判断自己是否在一个地方转圈，一个很好的方法就是在我们开始走的位置做一个标记，用来标注我们之前走过这个地方，如果未来我们又能发现这个标记，那么就说明我们绕圈了。

把这种思路对应在题目中，就是设置一个标记来表示我是否走过这个地方，如果走过我在后续遍历过程中又能回到这个地方，那么就说明链表存在环状结构，如果走到目的地（结尾），发现还是没有经历过标记点，那么就说明不存在环状结构，返回false。

如何标记？因为我们走的每一个点是一个ListNode对象，而对象的唯一标识就是它的引用或者hash值了吧？因此我们可以使用一个hashMap，用来存储每一个走过位置的hash，如果在后续遍历过程中还能匹配到之前走过的hash，那么就说明出现环状结构了。

代码思路：

1. 定义一个hashMap

2. 遍历链表，没走过一个节点之前先判断该节点是否在hashMap存在，如果存在直接返回true

3. 如果遍历完毕所有节点都没有返回false，那么说明不存在环状结构，返回false

3. 代码实现

3.1 思路一

3.2 思路二

使用哈希表——对比引用

使用哈希表——对比hash值

4. 相关复杂度分析

对于给出的三种解决环形链表问题的方法，我们来分析它们的时间和空间复杂度：

思路1：使用快慢指针

• 时间复杂度：O(n)，其中 n 是链表的长度。快指针每次移动两步，慢指针每次移动一步，因此快指针最多移动 n/2 次，慢指针最多移动 n 次，整体遍历的时间复杂度为 O(n)。

• 空间复杂度：O(1)，只使用了常数级别的额外空间。

思路2：使用哈希表（对比引用）

• 时间复杂度：O(n)，其中 n 是链表的长度。遍历链表需要 O(n) 的时间，同时在哈希表中查找节点是否存在的时间复杂度是 O(1)。

• 空间复杂度：O(n)，需要使用一个哈希表来存储链表中的节点，因此空间复杂度是 O(n)，其中 n 是链表的长度。

思路3：使用哈希表（对比哈希值）

• 时间复杂度：O(n)，其中 n 是链表的长度。与思路2相似，遍历链表需要 O(n) 的时间，同时在哈希表中查找哈希值是否存在的时间复杂度是 O(1)。

• 空间复杂度：O(n)，需要使用一个哈希表来存储链表中的节点的哈希值，因此空间复杂度是 O(n)，其中 n 是链表的长度。