刻意练习：LeetCode实战 -- Task09. 环形链表
背景
本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。
本次任务的知识点：链表
链表（Linked List） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里除了存放本身数据（data fields）之外还存放其后继节点的指针（Pointer）。
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表有很多种不同的类型：单向链表，双向链表以及循环链表。
题目
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
实现
第一种：利用Hash的方式
通过检查一个结点此前是否被访问过来判断链表是否为环形链表。
- 状态：通过
- 执行用时：172 ms, 在所有 C# 提交中击败了 8.84% 的用户
- 内存消耗：26.9 MB, 在所有 C# 提交中击败了 5.17% 的用户
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) {* val = x;* next = null;* }* }*/public class Solution
{public bool HasCycle(ListNode head) {HashSet<ListNode> hashSet = new HashSet<ListNode>();hashSet.Add(head);while (head != null){head = head.next;if (head == null)return false;if (hashSet.Contains(head))return true;hashSet.Add(head);}return false; }
}
Python 语言
- 执行结果：通过
- 执行用时：88 ms, 在所有 Python3 提交中击败了 16.80% 的用户
- 内存消耗：16.9 MB, 在所有 Python3 提交中击败了 7.04% 的用户
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:hashset = set()hashset.add(head)while head is not None:head = head.nextif head is None:return Falseif head in hashset:return Truehashset.add(head)return False
第二种：利用双指针的方式
- 状态：通过
- 执行用时: 112 ms, 在所有 C# 提交中击败了 98.43% 的用户
- 内存消耗: 24.9 MB, 在所有 C# 提交中击败了 5.13% 的用户
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public bool HasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if (fast == slow)return true;}return false;}
}
Python 语言
- 执行结果：通过
- 执行用时：56 ms, 在所有 Python3 提交中击败了 60.97% 的用户
- 内存消耗：16.6 MB, 在所有 Python3 提交中击败了 11.81% 的用户
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:fast = headslow = headwhile fast is not None and fast.next is not None:fast = fast.next.nextslow = slow.nextif fast == slow:return Truereturn False
来源
- https://leetcode-cn.com/problems/linked-list-cycle/submissions/
往期活动
LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！
- Python基础刻意练习活动即将开启，你参加吗？
- Task01：变量、运算符与数据类型
- Task02：条件与循环
- Task03：列表与元组
- Task04：字符串与序列
- Task05：函数与Lambda表达式
- Task06：字典与集合
- Task07：文件与文件系统
- Task08：异常处理
- Task09：else 与 with 语句
- Task10：类与对象
- Task11：魔法方法
- Task12：模块
我是 终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。
我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。
愿我们一起学习，一起进步，相互陪伴，共同成长。
后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：
相关文章：
CentOS学习笔记 - 9. docker maven编译基于gofabric8的java应用镜像
2019独角兽企业重金招聘Python工程师标准>>> 续上一篇 1. 修改java工程的pom.xml ， 加入docker编译插件 <plugin><groupId>com.spotify</groupId><artifactId>docker-maven-plugin</artifactId><version>1.0.0</…
Java虚拟机中获得Runtime实例的方法是什么?
Runtime类用于表示Java虚拟机运行时的状态，它用于封装Java虚拟机进程。每次使用“java”命令启动Java虚拟机时都会对应一个Runtime实例，并且只有一个实例，应用程序会通过该实例与其运行时的环境相连。应用程序不能创建自己的Runtime实例&…
仿百度文库方案[openoffice.org 3+swftools+flexpaper](三) 之 使用JODConverter将office文档转换为pdf...
第三步，使用JODConverter将office文档转换为pdf JODConverter是一个java的OpenDucument文件转换器，可以进行许多文件格式的转换，它利用 OpenOffice来进行转换工作，它能进行以下的转换工作： 1.Microsoft Office格式转换…
刻意练习：LeetCode实战 -- Task10. 两数相加
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
Ether-channel 以太网通道
Ether-channel通常称之为以太网链路捆绑，或者叫链路汇聚，链路聚合。作用：将多个类似的接口，捆绑成一个逻辑接口，从而增加设备之间的传输带宽增加设备之间的连接可靠性不但可以在链路设备之间形成链路备份，还…
web前端开发培训有哪些学习阶段
web前端技术主要针对于移动互联网是比较多的，对于零基础的同学来说前期主要学习基本的静态布局，HTML CSS，下面是web前端开发培训有哪些学习阶段的具体内容。 web前端开发培训有哪些学习阶段? 一、html5如何学习 1.HTML5 CSS3 JQ …
自己动手重新实现LINQ to Objects: 9 - SelectMany
本文翻译自Jon Skeet的系列博文“Edulinq”。 本篇原文地址： http://msmvps.com/blogs/jon_skeet/archive/2010/12/27/reimplementing-linq-to-objects-part-9-selectmany.aspx 我们接下来要实现的这个操作符是LINQ中最重要的操作符。大多数（或者是全部…
1.8 centos7 的PATH、cp/mv/文档查看命令介绍
环境变量PATH什么是环境变量？环境变量一般是指在操作系统中用来指定操作系统运行环境的一些参数，如：临时文件夹位置和系统文件夹位置等。[rootcentos7 ~]# echo $PATH #查看PATH环境变量 /usr/local/sbin:/usr/local/bin:/usr/sbin…
刻意练习：LeetCode实战 -- Task11. 删除链表的倒数第N个节点
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
https和http有什么区别?看下面介绍就知道了!
https和http有什么区别?相信很多还在学习软测的同学们，都会有遇到这种问题，下面就是小编给大家介绍的http相关的知识 。 一、http和https基本概念 1. HTTP：是互联网上应用最为广泛的一种网络协议，是一个客户端和服务器端请求和应…
C#图片灰度处理(位深度24→位深度8),用灰度数组byte[]新建一个8位灰度图像Bitmap 。...
原文:C#图片灰度处理(位深度24→位深度8) #region 灰度处理/// <summary>/// 将源图像灰度化，并转化为8位灰度图像。/// </summary>/// <param name"original"> 源图像。 </param>/// <returns> 8位灰度图像。 </return…
日期NSDate的使用
日期类NSDate,存储的是世界标准时(UTC)，输出时需要根据时区转换为本地时间方法description字符串以GMT0展示日期如：2011-11-16 07:02:25 0000测试的北京时间：2011-11-16 15:02:25.324/))))((((/格式化日期类型，使用NSDateFormatte…
刻意练习：LeetCode实战 -- Task12. 合并K个排序链表
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
软测培训机构哪个比较好
软件测试这个岗位是软件开发过程中非常重要的一步，一个软件的开发是少不了软测工程师的，近几年，软测的发展前景越来越可观，很多人都想学习软测技术，那么市面上软测培训机构哪个比较好呢?来看看下面的详细介绍。 软测培…
刻意练习：LeetCode实战 -- Task13. 罗马数字转整数
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
[翻译]ASP.NET MVC 3 开发的20个秘诀（十二）[20 Recipes for Programming MVC 3]：缩放图片尺寸创建缩略图...
议题 用户上传到网站上的大多数的图片都是大尺寸的照片，通常在用户想看完整图片之前网站会展示出这些图片或照片的缩略图。 解决方案 使用以下的类来调整上传的图片文件的宽和高：FileStream，Image，Bitmap和Graphics。 讨论 在下面…
Vue.js双向绑定的实现原理
Vue.js 最核心的功能有两个，一是响应式的数据绑定系统，二是组件系统。本文仅探究双向绑定是怎样实现的。先讲涉及的知识点，再用简化得不能再简化的代码实现一个简单的 hello world 示例。 一、访问器属性 访问器属性是对象中的一种特殊属性&a…
学习UI设计的一些小技巧你会了吗
最近有很多小伙伴都在学习UI设计技术，对于如今的互联网行业，UI设计这个岗位的需求量确实非常大，发展空间比较好，下面小编就为大家整理一些学习UI设计的一些小技巧，希望能够帮助到正在学习UI设计的同学。 学习UI设计的一…
30个精美的模板，贺卡，图形圣诞素材
圣诞节离我们越来越近了，当我们送礼物给我们所爱的，花时间与家人欢乐。我们都喜欢收到圣诞贺卡。，如果你有大量的生活很远的亲戚的话，你可以给他一个Email。本文介绍了从商场收集的30个圣诞素材，你可以创造圣诞的心情&…
刻意练习：LeetCode实战 -- Task14. 最长公共前缀
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
6.1.1 验证注解的使用
数据注解特性定义在名称空间System.ComponentModel.DataAnnotations 中(但接下来 将看到，有些特性不是定义在这个名称空间中)。它们提供了服务器端验证的功能，当在模 型的属性上使用这些特性之一时，框架也支持客户端验证。在名称空间DataAnno…
Javascript创建数组的方式你了解了吗
Javascript数组 数组(Array)是一种复杂的数据类型，它属于Object(对象)类型，用来将一组数组合在一起，通过一个变量就可以访问一组数据。在使用数组时，经常会搭配循环语句使用，从而很方便地对一组数据进行处理。 创建数组…
loadrunner另类玩法【测试帮日记公开课】
https://edu.51cto.com/course/10658.html
刻意练习：LeetCode实战 -- Task15. 有效的括号
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
对口令协议的几种攻击方式
1、窃听入侵者搭线窃听，试图从正在进行的通信中获得有用的信息。 2、重放入侵者记录过去通信中的消息并在以后的通信中重放它们。 3、中间人攻击入侵拦截各主体之间的消息，并用自己的消息来取代它们。在向服务器发送的消息中他假冒用户的身份，…
初学者如何学Java开发
初学者如何学Java开发?这是很多人都比较关注的一个问题，尤其是对于零基础想要学习java的同学，java技术语言包含的知识点有很多，下面小编就给大家整理一些建议希望可以帮到初学者们。 初学者如何学Java开发? 1.教材的选择 学习Java书籍的选择…
[算法] [常微分方程] [欧拉法 改进欧拉法 经典R-K算法]
1 #include<iostream>2 #include<cmath>3 #include<cstdio>4 #include<iomanip>5 using namespace std;6 double h0.1;//步差7 double xi[11]{0};8 double ol_yi[11]{1};9 double gol_yi[11]{1}; 10 double rk_yi[11]{1}; 11 double real_yi[11]{1}; 1…
刻意练习：LeetCode实战 -- Task16. 无重复字符的最长子串
背景 本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了…
轻松实现QQ用户接入
1. 申请合作伙伴ID (PID),Key (PKey)2. 发送请求 https://graph.qq.com/oauth2.0/authorize?response_typecode&client_id100000353&redirect_urihttp://www.wodongni.com/loginReturn.aspx redirect_uri:回传URL client_id: 合作伙伴ID (PID) 返回： …
web前端培训之Javascript如何改变数组的长度?
修改数组长度 使用“数组名.length”可以获取或修改数组的长度。数组长度的计算方式为数组中元素的最大索引值加1，示例代码如下。 var arr [a, b, c]; console.log(arr.length); //输出结果:3 在上述代码中，数组中最后一个元素是c，该元素的索…