LeetCode 141:环形链表 Linked List Cycle
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos
which represents the position (0-indexed) in the linked list where tail connects to. If pos
is -1
, then there is no cycle in the linked list.
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1 输出:false 解释:链表中没有环。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
解题思路:
从头节点向后遍历整个链表只要遍历到节点为 null ,就证明不是环形,而如果遍历到一个节点的地址之前存在过就证明有环。
1、哈希表:
解决重复问题最容易想到的数据结构就是哈希表,哈希表添加节点时只要发现节点已经存在了,证明就有环形链表。并且哈希表查找和插入复杂度都为O(1),但是空间复杂度会随着原链表长度而增大:O(n),总的来说:
- 时间复杂度:O(n),虽然哈希表的查找和添加操作的时间复杂度是 O(1) ,但是先需要遍历链表然后插入,遍历的复杂度是O(n)
- 空间复杂度:O(n),最多需要保存链表的 n个节点
2、双指针:
这道题就如同小学跑步问题,假设有两个人(双指针)一个快一个慢,不停地向前跑,如果跑得快的那个最后到终点了(遇到空节点 null),就证明是直线跑道(没有环形链表)。
如果是存在环形跑道(环形链表):两个人一起跑步(双指针)一个快一个慢,那么这两个人因为速度不同,在环形跑道里跑得快的那个人一定会追上慢的。即两个指针相遇了,证明存在环形链表。
空间复杂度为O(1),即进阶要求的常量内存。
哈希表解题:
Java:
public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false;//如果是空链表直接返回 Set<ListNode> nodeSet = new HashSet<>();//构造哈希表 while (head.next != null) {//链表下一个不为空 if (nodeSet.contains(head)) return true;//哈希表包含该节点则存在环形链表 nodeSet.add(head);//加入节点 head = head.next;//下移一位 } return false; } }
Python:
class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head is None: return False hashSet=set()#构造集合 while(head.next is not None): if head in hashSet:#是否已存在 return True hashSet.add(head) head=head.next return False
双指针解题:
Java:
public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) {//快指针及其下一位是否为空 slow = slow.next; fast = fast.next.next; if (slow == fast) {//如果相遇,存在环形链表 return true; } } return false; } }
Python:
class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if head is None or head.next is None: return False slow, fast = head, head while fast is not None and fast.next is not None: slow, fast = slow.next, fast.next.next if slow == fast: return True return False
扩展:
python 中is 与 == 区别 :
is 用于判断两个变量引用对象(即内存地址)是否为同一个, == 用于判断引用变量的值是否相等。
而Python出于对性能的考虑,不可变对象、同一代码块中的对象、值相同的对象,都不会重复创建,而是直接引用已经存在的对象。
欢迎关注公众号:爱写bug,一起学习。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
JavaScript深入浅出第4课:V8引擎是如何工作的?
摘要: 性能彪悍的V8引擎。 《JavaScript深入浅出》系列: JavaScript深入浅出第1课:箭头函数中的this究竟是什么鬼? JavaScript深入浅出第2课:函数是一等公民是什么意思呢? JavaScript深入浅出第3课:什么是垃圾回收算法? JavaScript深入浅出第4课:V8是如何工作的? 最近,JavaScript生态系统又多了2个非常硬核的项目。 大神Fabrice Bellard发布了一个新的JS引擎QuickJS,可以将JavaScript源码转换为C语言代码,然后再使用系统编译器(gcc或者clang)生成可执行文件。 Facebook为React Native开发了新的JS引擎Hermes,用于优化安卓端的性能。它可以在构建APP的时候将JavaScript源码编译为Bytecode,从而减少APK大小、减少内存使用,提高APP启动速度。 作为JavaScript程序员,只有极少数人有机会和能力去实现一个JS引擎,但是理解JS引擎还是很有必要的。本文将介绍一下V8引擎的原理,希望可以给大家一些帮助。 JavaScript引擎 我们写的JavaS...
- 下一篇
网站漏洞修复之Discuz X3.4远程代码执行漏洞
近期在对discuz x3.4进行全面的网站渗透测试的时候,发现discuz多国语言版存在远程代码执行漏洞,该漏洞可导致论坛被直接上传webshell,直接远程获取管理员权限,linux服务器可以直接执行系统命令,危害性较大,关于该discuz漏洞的详情,我们来详细的分析看下。 discuz漏洞影响范围:discuz x3.4 discuz x3.3 discuz x3.2,版本都受该网站漏洞的影响,漏洞产生的原因是在source目录下function文件夹里function_core.php代码里的cookies与语言language参数值并没有详细的进行安全过滤与检测,导致可以插入恶意的代码到数据库,并远程执行恶意代码,可获取webshell权限。 discuz漏洞分析 我们来看下刚才产生漏洞的代码,在第535行往下看,有一段代码是这样写的,默认网站系统将缓存数据存储在data文件夹里的template目录中,缓存文件名的命名是由前面的discuz_lang参数进行控制来命令的,漏洞产生的原因就在这里。那这个discuz_lang参数的值是从来获取来的呢? 我们跟进分析网站代码,可...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- Docker安装Oracle12C,快速搭建Oracle学习环境
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Mario游戏-低调大师作品