LeetCode-141. 环形链表(java)

一、前言：

👨‍🎓作者：bug菌 ✏️博客：​​CSDN​​​、​​掘金​​等 💌公众号：​​猿圈奇妙屋​​ 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

题目：

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

注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

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

具体请看如下示例：

示例 1:

LeetCode-141. 环形链表(java)_leetcode

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

示例 2:

LeetCode-141. 环形链表(java)_leetcode_03

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

示例 3:

LeetCode-141. 环形链表(java)_leetcode_05

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

提示：

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

题目来源：​​LeetCode官网​​ 题目难度：⭐⭐

三、思路分析：

       其实我刚拿到这题的时候，给我的第一反应就是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。具体做法如下:

• 定义一个哈希表来存储所有已经访问过的节点。
• 每遍历到一个节点，如果该节点存在于哈希表中，则说明该链表是环形链表；否则就将该节点加入哈希表中。
• 重复这一过程，直到遍历完整个链表即可。
• 若完整遍历完，则说明该链表不是环形，返回false即可。

四、算法实现：

AC代码

具体算法代码实现如下：

public class Solution {
    public boolean hasCycle(ListNode head) {

        //定义一个set
        Set<ListNode> nodeSet = new HashSet<ListNode>();
        while (head != null) {
            //如果nodeSet添加相同节点会返回false 
            if (!nodeSet.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

五、总结：

哈希表法之leetcode提交运行结果截图如下：

LeetCode-141. 环形链表(java)_leetcode_08

复杂度分析：

• 时间复杂度：O(n)。其中 n 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。 空间复杂度：O(n)。其中 n 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

       这题其实找到思路还是相对简单的，就是害怕有的同学会被套进去，人家只是演示告诉你通过pos来告知你是否是环形且指向第几个节点。我写的也是最通常也是最能想到的一种思路。

       再者，解题道路千万条，欢迎小伙伴们脑洞大开，如果你们有啥更好的想法或者思路，欢迎评论区告诉我哦，大家一起互相借鉴互相学习，方能成长的更快。

好啦，以上就是本期的所有内容啦，咱们下期见咯。