【Leetcode链表】环形链表(141)
2024-10-08 02:18:33
题目
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 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,遍历整个链表,看能不能走到尾部NULL,如果有NULL则无环,如果没有NULL就可能是有环,也可能链表太长会运行超时,这种方法不可取
2,用哈希表,依次遍历链表set存储走过的点 ———— 时间复杂度O(n),空间复杂度O(n)
3,快慢指针,如果有环快指针一定会追上慢指针,两者相遇即有环,快指针走到NULL即无环 ———— 时间复杂度O(n),空间复杂度O(1)
通过代码如下:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
## 哈希set,对比走过的点
class Solution:
def hasCycle(self, head: ListNode) -> bool:
s = set()
while head:
if head in s:
return True
s.add(head)
head = head.next
return False
## 时间复杂度O(n),空间复杂度O(n)
## 快慢指针,快指针一次走两步,慢指针走一步,如果有环快慢一定会相遇
# class Solution:
# def hasCycle(self, head: ListNode) -> bool:
# f = s = head
# while f and f.next: # 一定是f.next不能为空,因为f走得快
# f = f.next.next
# s = s.next
# if f == s:
# return True
# return False
## 时间复杂度O(n),空间复杂度O(1)
最新文章
- hadoop 2.7.2 + zookeeper 高可用集群部署
- JS实现常用排序算法—经典的轮子值得再造
- 大型网站提速关键技术(页面静态化,memcached,MySql优化)(三)
- Oracle 11g数据库详细安装步骤图解
- RDIFramework.NET ━ 9.5 组织机构管理 ━ Web部分
- 【循序渐进学Python】7.面向对象的核心——类型(上)
- JobTracker启动流程源码级分析
- Out of resources when opening file 错误解决
- [STL]算法的泛化过程
- WCF简介
- python【第十七篇】jQuery
- C#关于ref的用法(多个实参值的传递)
- 每天一个JS 小demo之日历制作。主要知识点:日期函数
- 用ESP8266+android,制作自己的WIFI小车
- Python爬虫(十四)_BeautifulSoup4 解析器
- 【转】awk 里的substr函数用法举例
- 关于 js中replace 特殊符号 ‘.’ 的问题
- ubuntu安装chkconfig.deb系统服务管理工具
- Python线程和协程-day10
- js 模拟css3 动画1
热门文章
- Luogu P3106 [USACO14OPEN]GPS的决斗Dueling GPS's(最短路)
- 关于distinct 和group by的去重逻辑浅析
- iscroll的滑动效果
- ifconfig命令为centos linux系统配置临时的局域名IP、网关以及子网掩码
- Amazon EBS的功能更新
- IntelliJ IDEA 中如何查看一个类的所有继承关系(当前类的所有继承关系图)
- CSS Tools: Reset CSS
- C++学习笔记(2)---2.5 C++函数编译原理和成员函数的实现
- mac Chrome 快捷键
- 集合-Collection接口