首页 > 其他分享 >力扣: 环形链表

力扣: 环形链表

时间:2024-08-29 14:50:34浏览次数:11  
标签:力扣 head return cur 环形 next 链表 null

文章目录

在这里插入图片描述


需求

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

提示:

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

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?


Map

public boolean hasCycle(ListNode head) {
    if( head == null || head.next == null ){
        return false;
    }
    Map<ListNode, Integer> map = new HashMap();
    ListNode cur = head; 
    while( cur != null ){
        if( map.containsKey(cur) ){
            return true;
        }else{
            map.put(cur, 1);
        }
        cur = cur.next;
    } 
    return false;
}

执行结果:
在这里插入图片描述

Set

public boolean hasCycle(ListNode head) {
    if( head == null || head.next == null ){
        return false;
    }
    Set<ListNode> set = new HashSet();
    ListNode cur = head; 
    while( cur != null ){
        if( !set.add(cur) ){
            return true;
        }
        cur = cur.next;
    } 
    return false;
}

执行结果:
在这里插入图片描述


快慢指针

public boolean hasCycle(ListNode head) {
    if( head == null || head.next == null ){
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;

    while( fast != null && fast.next != null ){
        fast = fast.next.next;
        slow = slow.next;
        //	相遇
        if( slow == fast ){
            return true;
        }
    }
    return false;
}

执行结果:

在这里插入图片描述


结尾

以上 是我对这道算法的一些遐想和延伸, 可能不是最优解, 但是算法的优化嘛 本身就是一个思索的过程, 能在这个思索和迭代的过程中有所收获和乐趣就是在成长了, 欢迎大家一起来交流更多的解答…




标签:力扣,head,return,cur,环形,next,链表,null
From: https://blog.csdn.net/Snowyyds/article/details/141677248

相关文章

  • 数据结构与算法(循环链表,双向链表)
    循环链表最后一个元素指向首元素带尾指针的循环链表合并双向链表双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior,这样链表中就形成了有两个方向不同的链,故称为双向链表双向链表插入操作思路代码删除操作思路代码三种链表比较顺序表......
  • 力扣热题100_贪心算法_45_跳跃游戏
    文章目录题目链接解题思路解题代码题目链接45.跳跃游戏II给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向前跳转的最大长度。换句话说,如果你在nums[i]处,你可以跳转到任意nums[i+j]处:0<=j<=nums[i]......
  • 数据结构——单向链表
    链表1.空间可以不连续(理论上长度是无限的)2.访问元素不方便3.链表需要更大的空间存放数据和节点地址4.链表的插入和删除效率很高O(1)单向链表无头单向链表,节点插入在头的话,每次头结点都会变,所以有了有头链表,头结点的pNext总是指向链表的第一个节点1.创建空链表//创建空......
  • 信息学奥赛初赛天天练-77-NOIP2015普及组-基础题2-二进制、连通图、最小生成树、链表
    NOIP2015普及组基础题24在计算机内部用来传送、存贮、加工处理的数据或指令都是以()形式进行的A二进制码B八进制码C十进制码D智能拼音码5下列说法正确的是()ACPU的主要任务是执行数据运算和程序控制B存储器具有记忆能力,其中信息任何时候都不会......
  • 3217. 从链表中移除在数组中存在的节点
    从链表中移除在数组中存在的节点给你一个整数数组nums和一个链表的头节点head。从链表中移除所有存在于nums中的节点后,返回修改后的链表的头节点。示例1:输入:nums=[1,2,3],head=[1,2,3,4,5]输出:[4,5]解释:移除数值为1,2和3的节点。示例2:输入:nums=[......
  • 82. 删除排序链表中的重复元素 II
    传送锚点:力扣给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],val=7输......
  • 【力扣】3145.大数组元素的乘积
    题目描述一个非负整数 x 的 强数组 指的是满足元素为2的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明,x 对应的强数组是独一无二的。数字二进制表示强数组100001[1]801000[8]1001010[2,8]1301101[1,4,8]2310111[1,2,4,16]......
  • 数据结构之链表
    C++中常见的数据结构-CSDN博客目录一、链表的定义二、链表的创建三、链表的遍历四、链表的插入五、链表的删除六、总结 链表是计算机科学中常见的一种数据结构,c/c++语言中也有着丰富的链表操作函数库。本文将从链表的定义、创建、遍历、插入、删除等多个方面进行详细......
  • 给自己复盘的随想录笔记-链表练习题(在整理ing)
    删除链表的倒数第N个节点双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样的,但要注意一些细节。分为如下几步:推荐大家使用虚拟头结点,这样方便处理删除实际头结点的逻辑,定......
  • 56. 合并区间【 力扣(LeetCode) 】
    一、题目描述  以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。二、测试用例示例1:输入:intervals=[[1,3],[2,6],[8,10],[15,18]]输......