面试经典150题——环形链表
Suffering, for the weak is the tomb of death, and for the strong is the soil of germinal ambition.
1. 题目描述
2. 题目分析与解析
2.1 思路一
这个题目就是判断一个链表有没有环，其实我们之讲过一个题目，就实现了判断链表有没有环的步骤：面试经典150题——快乐数，并且还有图示，就是使用快慢指针法，因此在本篇文章中就不过多赘述了，直接给出代码思路。
代码思路：
-
定义两个指针，分别表示快慢指针
-
让快指针以2的速度前进，慢指针以1的速度前进
-
如果两个指针相交，说明链表中存在环结构，返回true
-
如果遍历到结尾仍然没有返回false就说明没有环，返回false
2.2 思路二
因为我们用一种很简单的思路如何判断自己是否在一个地方转圈，一个很好的方法就是在我们开始走的位置做一个标记，用来标注我们之前走过这个地方，如果未来我们又能发现这个标记，那么就说明我们绕圈了。
把这种思路对应在题目中，就是设置一个标记来表示我是否走过这个地方，如果走过我在后续遍历过程中又能回到这个地方，那么就说明链表存在环状结构，如果走到目的地（结尾），发现还是没有经历过标记点，那么就说明不存在环状结构，返回false。
如何标记？因为我们走的每一个点是一个ListNode对象，而对象的唯一标识就是它的引用或者hash值了吧？因此我们可以使用一个hashMap，用来存储每一个走过位置的hash，如果在后续遍历过程中还能匹配到之前走过的hash，那么就说明出现环状结构了。
代码思路：
-
定义一个hashMap
-
遍历链表，没走过一个节点之前先判断该节点是否在hashMap存在，如果存在直接返回true
-
如果遍历完毕所有节点都没有返回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 是链表的长度。
原文地址：https://blog.csdn.net/m0_60388871/article/details/136538281
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！