文档章节

141. 环形链表

o
 osc_gu9d45li
发布于 2019/04/07 22:09
字数 919
阅读 0
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

问题描述

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

解决方案

快慢指针法

想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况:

  1. 如果没有环,快指针将停在链表的末尾。
  2. 如果有环,快指针最终将与慢指针相遇。

所以剩下的问题是:

这两个指针的适当速度应该是多少?

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

时间复杂度:O(n)

空间复杂度:O(1)

show me the code

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        quick_pointer = slow_pointer = head             # 创建两个指针,分别记录一个快的遍历指针,和一个慢的便利指针

        while quick_pointer and quick_pointer.next:     # 当快指针为None,或快指针的下个一对象为None,说明不是环形链表
            slow_pointer = slow_pointer.next            # 慢指针前进一步
            quick_pointer = quick_pointer.next.next     # 快指针前进两步
            if slow_pointer == quick_pointer:           # 假如快指针等于慢指针,说明为环形链表
                return True
        return False

hash表存贮法

顺序遍历链表所有节点,若出现重复访问则说明有环,否则说明无环。这里注意不能用list保存访问过的节点,查找太慢了;用dict保存还要考虑到键不能是对象,所以这里采取以对象的id作为键的做法。

时间复杂度:O(n)

空间复杂度:O(n)

show me the code

class Solution2(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        my_dict = {}                        # 创建一个字典来保存已经遍历过节点的内存地址
        while head and head.next:           # 当快指针为None,或快指针的下个一对象为None,说明不是环形链表
            if id(head) in my_dict:         # 假如当前节点在字典中则说明是环形链表
                return True
            else:
                my_dict[id(head)] = True    # 将当前节点加入到字典中

        return False

逆转链表检测法

倘若一个链表存在环,那么将这个链表反转,反转后的链表和原链表具有相同的head。证明起来比较麻烦,可以在纸上画一画来验证。

时间复杂度:O(n)

空间复杂度:O(n)

show me the code

class Solution3(object):
    def reverse_list(self, head):
        before = after = None
        while head:
            after = head.next # 保存当前节点的下一个节点
            head.next = before # 将当前节点的下一题个节点替换为当前节点的上一个节点
            before = head # 将上一个节点,往前移动,变为当前节点
            head = after # 当前节点向前移动
        return before # 返回反转完成后的头结点

    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head and head.next and head == self.reverse_list(head): # 加入反转后的头结点与原先的头结点相同,则说明有环
            return True
        return False
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
硬实时操作系统--Raw OS

Raw-OS 起飞于2012年,Raw-OS志在制作中国人自己的最优秀硬实时操作系统。 Raw-OS 操作系统特性 内核最大关中断时间无限接近0us, s3c2440系统最大关中断时间实测0.8us。 支持idle任务级别的事...

jorya_txj
2013/03/19
6.3K
1
JCF框架源码分析系列-ArrayList(二)

1、揭开ArrayList真面目 作者将在本文详细赘述日常开发中最常用集合类-ArrayList,本次JCF源码分析基于JDK1.7,主要从以下几个方向分析: UML类图关系 数据结构 接口介绍 常用、重要方法的实...

Ambitor
2015/11/30
385
0
学生管理系统——基于双向循环链表

基于双向循环链表实现的学生管理系统,包括初始化,插入,删除,查抄,保存,自动按照姓名排序功能,退出并保存功能。 实现思想是将程序的各个部分划分为三个层次。主函数为界面层,即客户端...

穿靴子的猫LJL
2015/09/03
5.8K
39
如何在设计PCB时增强防静电ESD功能

如何在设计PCB时增强防静电ESD功能 在PCB设计 中,可以通过分层、恰当的布局布线和安装实现PCB的抗ESD设计。在设计过程中,通过预测可以将绝大多数设计修改仅限 于增减元器件。通过调整PCB布...

mini2014
2014/08/14
15
0
C++中的STL标准库到底该不该用?

我正在做一个软件,因为是C++开发,所以我当时就决定了使用STL标准库,到目前为止,所有的字符串、链表等全部都是用的STL。 但是我最近越来越感到不舒服,STL好像并没有我认为的好用。首先,...

clonne
2012/06/21
8.5W
79

没有更多内容

加载失败,请刷新页面

加载更多

OSPF综合实验

OSPF开放路径最短选择优先协议(IGP协议、链路状态协议) 支持大型网络,通过彼此交互hello建立邻居关系,在通过彼此交互的LSA通过SPF算法算出最优路由的到自己去往其他节点路径。 OSPF的DR、...

osc_qmxpov5s
14分钟前
0
0
vmlogin多平台·多账号·安全提速系统·稳定浏览器指纹环境

VMLogin-稳定浏览器指纹环境,Cookie隔离,稳定,更高效,更智能的多账号管,从超级浏览器开始,让你的跨境之旅更便捷! VMLogin生成多个唯一指纹浏览器,每个指纹浏览器都是相互隔离的。 可以...

VMlogin中文版防关联浏览器
14分钟前
0
0
Buurst SoftNAS操作手册—Part1 如何在AWS上部署SoftNAS

前言 Buurst SoftNAS为企业提供高性能、易管理、高可用、极具经济效益的存储服务,无论是在私有云还是公有云环境下均可实现一键部署。Buurst SoftNAS可为企业提供软件定义NAS文件管理器并提供...

osc_cyo5y1ey
15分钟前
0
0
《闲扯Redis十》Redis 跳跃表的结构实现

一、前言 Redis 提供了5种数据类型:String(字符串)、Hash(哈希)、List(列表)、Set(集合)、Zset(有序集合),理解每种数据类型的特点对于redis的开发和运维非常重要。 原文解析:h...

大道七哥
16分钟前
0
0
BGP综合实验

BGP边界网关协议 BGP是目前使用的唯一的自治系统间的路由协议,它是一种矢量路由协议,基于TCP的179号端口,它采用单播增量更新的方式更新路由,与其他的路由协议不同的是,BGP只要TCP可达,...

osc_tybx1rlt
16分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部