【Leetcode链表】环形链表 II(142)
2024-09-02 15:48:25
题目
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。
进阶:
你是否可以不用额外空间解决此题?
解答
两种方法:
1,用哈希表,依次遍历链表set存储走过的点,遇见重复的就是环入口 ———— 时间复杂度O(n),空间复杂度O(n)
2,快慢指针,指针在环内相遇的位置到环入口的距离 == 表头到环入口的距离,两者相向而行,相遇位置就是环入口 ———— 时间复杂度O(n²),空间复杂度O(1)
通过代码如下:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# 哈希表:时间复杂度O(n),空间复杂度O(n)
# class Solution:
# def detectCycle(self, head: ListNode) -> ListNode:
# s = set()
# while head:
# if head in s:
# return head
# s.add(head)
# head = head.next
# return None
# 指针法:时间复杂度O(n²),空间复杂度O(1)
# 1,快慢双指针找到相遇位置
# 2,相遇位置到环入口的距离 == 表头到环入口的距离,两者相向而行,相遇位置就是环入口
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
f = s = h = head # h记录表头
while f and f.next:
s = s.next
f = f.next.next
if f == s: # 相遇了,开始和表头相对走,找环入口
p = f
while h!=p:
h = h.next
p = p.next
return h
head = head.next
return None
最新文章
- eclipse调试java程序的九个技巧
- SAP销售模块塑工常见问题和解决方案(自己收藏)
- SQL server同时删除多个表
- C#连接数据库SQL,并转换成list形式
- 购物车catslider简单的多商品分类滑动
- 使用新版Android Studio检测内存泄露和性能
- windows 7 + vs2010 sp1编译 x64位版qt4
- 读书笔记——《图解TCP/IP》(4/4)
- 百度地图API示例之添加自定义控件
- Sublime Text—安装
- hadoop 2.0 详细配置教程(转载)
- c#--Redis帮助类
- P2255 [USACO14JAN]记录奥林比克
- JavaScript 实现textarea限制输入字数, 输入框字数实时统计更新,输入框实时字数计算移动端bug解决
- C#中的as关键字
- 关于QList<;T>;的内存释放
- go语言面向对象编程之类型系统
- 初始化vue项目,报错This is probably not a problem with npm,there is likely additional logging output above
- JQuery如何实现双击事件时不触发单击事件
- MySQL Split 函数
热门文章
- LA4670 Dominating Patterns AC自动机模板
- bzoj 4004 [JLOI2015]装备购买——拟阵证明贪心+线性基
- mybatis深入理解(五)-----MyBatis的一级缓存实现详解 及使用注意事项
- springmvc 传参Required String parameter &#39;xxxx&#39; is not present
- neo4j批量导入neo4j-import
- 阿里毕玄:来测试下你的Java编程能力
- leetcode 1-20 easy
- Maven常用命令备忘
- Hdu 1156
- 性能测试工具---loadrunner