LeetCode#141-Linked List Cycle-环形链表
一、题目
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 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)(即,常量)内存解决此问题吗?
二、题解
- 解法1:哈希表
遍历所有节点并把每个节点的引用存储到哈希表中。如果当前节点的引用已经存在于哈希表中,说明该链表是环形链表,返回 true;反之,则遍历到尾,即该节点的下一个节点为 null,该链表不是环形链表,返回 false。
时间复杂度:O(n),空间复杂度:O(n)。
function hasCycle($head) {
$hashMap = [];
$curr = $head;
while ($curr != null && $curr->next != null) {
if (in_array($curr, $hashMap)) {
return true;
}
$hashMap[] = $curr;
$curr = $curr->next;
}
return false;
}
- 解法2:双指针——快慢指针
快指针:一次两步
慢指针:一次一步
假设一个环形赛道,两个运动员 A 和 B,A 领先 B 一步:
在一个圆里,速度快的 A 在跑了 n 圈后,一定能遇到速度慢的 B
——对应链表,就是两个指针重合
如果不是圆,速度快的 A 一定先到达终点,则说明不存在环
——对应链表,就是结尾指针指向null
时间复杂度:O(n),空间复杂度:O(1)。
function hasCycle($head) {
if ($head == null || $head->next == null) {
return false;
}
//快慢指针
$slow = $head;
$fast = $head->next;
while ($slow != $fast) {
//没有环,fast走到链表尾部,fast为空或者fast的next为空
if ($fast == null || $fast->next == null) {
return false;
}
$slow = $slow->next;
$fast = $fast->next->next;
}
return true;
}
快慢指针法是看了题解后做出来的,一开始有点不明白:为什么快指针速度为 2,慢指针速度为 1?快指针速度不能为 3 甚至更大吗?
画图画了几遍,大概理解了:
fast 走 2 步,slow走 1 步,如果有环,则 fast 会碰到 slow 或者 fast 会走到 slow 的后面。
如果是 fast 走到 slow 后面,这时候两个指针每走一次它们之间的距离就会缩小 1,最后无论多远两个指针肯定会相遇。
但是如果是 fast 走 3 步,slow 走 1 步,同样是前面的情况,它们之间的距离每次缩小 2,最后 fast 又跑到 slow 前面去了,所以如果 fast 设置为 3,需要多加一个判断条件,见下面代码 while
处。
function hasCycle($head) {
if ($head == null || $head->next == null) {
return false;
}
//快慢指针
$slow = $head;
$fast = $head->next->next;
while ($slow != $fast || $slow->next != $fast) {
//没有环,fast走到链表尾部,fast为空或者fast的next为空
if ($fast == null || $fast->next == null) {
return false;
}
$slow = $slow->next;
$fast = $fast->next->next->next;
}
return true;
}
最新文章
- 算法与数据结构(2)--英雄会第三届在线编程大赛:几个bing
- Python 将pdf转换成txt(不处理图片)
- PHP打开PDO_MySQL扩展的配置方法
- Setup Factory
- 关于http接口开发中json格式数据编码问题处理
- jasmine 初探(一)
- C# 微信 企业号通知消息
- HDU1411 欧拉四面体
- Sql Server 里的向上取整、向下取整、四舍五入取整的实例!
- [CQOI2014]危桥
- sql判断日期是否为当前季度
- 小小知识点(一)——利用电脑自带的BitLocker对磁盘加密
- Android之Sqlite数据库
- 配置nginx1.8支持thinkPHP3.2 pathinfo模式
- MTStatusBarOverlay (状态栏,添加自定义内容库)
- Linux-Ubuntu14.04下mongodb安装部署
- 【CS231N】5、神经网络静态部分:数据预处理等
- Tomcat在Linux下的安装与配置
- 【BZOJ2314】士兵的放置 树形DP
- 中间件和auth模块
热门文章
- javascript中indexOf()和lastIndexOf()详解
- Mybatis总结一之Mybatis项目的创建
- Natas31 Writeup(Perl 远程命令执行)
- Jenkins分布式构建与并行构建
- SpringBoot2整合Redis多数据源
- go:内置函数 | 闭包 | 数组 | 切片 | 排序 | map | 锁
- python3爬虫爬取金庸小说所有角色
- 升级 nop 4.1 Incorrect syntax near 'OFFSET'. Invalid usage of the option NEXT in the FETCH statement.
- 面试刷题17:线程两次start()会发生什么?
- 北邮OJ-257- 最近公共祖先-软件14 java