算法通关村第一关——链表经典问题之判断是否有环

怼烎@ 2024-03-22 21:25 101阅读 0赞

### 链表中环的问题 ###

> 给定一个链表，判断链表中是否有环

#### 图解 ####

#### ![eeebb176d00f494a8cdc4862d11507df.png][] ####

#### 示例 ####

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

#### 思路 ####

> 判断是否有环，最容易的是使用哈希，遍历的时候将元素放入到set（或者map）中，如果有环，就一定会发生哈希碰撞，这个碰撞的位置就是环入口的位置

#### 代码实现 ####

/**
         * 题目：给定一个列表，判断是否有环
         * 示例：
         * 输入：head=[3,2,0,-4] pos=1
         * 输出：true
         * 解释：链表中有一个环，其尾部连接到第二个节点
         * @param head
         * @return
         */
        public Node detectCircle(Node head){
            Node pos = head;
            Set<Node> hash = new HashSet<>();
            while (pos != null) {
                if (hash.contains(pos)){
                    return pos;
                }else {
                    hash.add(pos);
                }
                pos = pos.next;
            }
            return null;
        }

####  ####

[eeebb176d00f494a8cdc4862d11507df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cba46bbf68ce459e8cdaa39dea9379a7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，101人围观）

还没有评论，来说两句吧...

相关阅读

相关算法通关村第一关——链表经典问题之判断是否有环

链表中环的问题 > 给定一个链表，判断链表中是否有环图解 ![eeebb176d00f494a8cdc4862d11507df.png][] 示例

怼烎@/ 2024年03月22日 21:25/ 0 赞/ 102 阅读

相关算法通关村第一关——链表经典问题之删除链表元素专题笔记

删除特定节点题目描述 > 给你一个链表的头节点head和一个整数val，请你删除链表汇总所有满足Node.val == val 的节点，并返回新的头节点示例

小灰灰/ 2024年03月22日 21:23/ 0 赞/ 90 阅读

相关算法通关村第一关——链表经典问题之双指针专题笔记

寻找中间节点题目描述 > 给定一个头节点为head的非空单链表，返回链表的中间节点；如果有两个中间节点，则返回第二个中间节点示例 > 示例1：

柔光的暖阳◎/ 2024年03月22日 21:02/ 0 赞/ 71 阅读

相关算法通关村第一关——链表经典问题之合并有序链表

合并两个链表题目描述 > 将两个有序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的解决思路 > 思路1：新建一个链表，

柔光的暖阳◎/ 2024年03月22日 20:59/ 0 赞/ 92 阅读

相关算法通关村第一关——链表经典问题之回文序列笔记

题目描述 > LeetCode234，这是一个简单且经典的链表题，判断一个链表是否为回文链表示例1 > 输入：1 -> 2 -> 2 ->1 > > 输出：

╰半夏微凉°/ 2024年03月22日 20:58/ 0 赞/ 79 阅读

相关算法通关村第一关——链表经典问题之两个链表第一个公共子节点笔记

问题描述 > 输入两个链表，找出它们的第一个公共子节点。如下图所示： ![8085ce8cffd2487cac88521f84997795.png][] > 两

落日映苍穹つ/ 2024年03月17日 21:02/ 0 赞/ 98 阅读

相关判断链表是否有环

/ 判断链表是否有环快慢指针 / public class Test2 { public static void main(S

Love The Way You Lie/ 2022年10月29日 07:45/ 0 赞/ 207 阅读

相关判断链表是否有环

![这里写图片描述][70] //判断链表有环 public boolean hasCycle(ListNode head) {

忘是亡心i/ 2022年05月23日 04:42/ 0 赞/ 234 阅读

相关判断链表是否有环？

题目描述有一个单向链表，链表当中有可能出现“环”，就像下图这样。如何用程序判断出这个链表是有环链表？ ![70][] 方法一：首先从头节点开始，依次遍历单链表的每

你的名字/ 2022年05月14日 03:56/ 0 赞/ 247 阅读

相关判断链表是否有环

给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？ 3、如何找出环的连接点在哪里？ 4、带环链表的长度是多少？解法

素颜马尾好姑娘i/ 2022年03月25日 14:42/ 0 赞/ 308 阅读