V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
kaolalicai
V2EX  ›  问与答

链表问题--如何判断链表有环?

  •  
  •   kaolalicai · 2019-05-19 16:42:51 +08:00 · 2404 次点击
    这是一个创建于 1775 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一、题目描述

    如果有一个单向链表,链表当中有可能出现"环",就像下图这样,如何判断这个链表是有环链表?

    二、解题思路

    方案一:暴力法

    从头节点,依次遍历单链表的每一个节点,每到一个新的节点就头节点重新遍历之前的所有的节点,对比此时的节点,如果相同,证明该节点遍历过两次,以此说明链表是有环的

    Node p = head.next
    while(p.next!==null){
        Node c = head
        while(c!==p){
            c=c.next
        }
        if(c.next!==p.next){
            return true
        }
        p = p.next
    }
    return false;
    

    此方案时间复杂度为O(n^2),空间复杂度为 O(1)

    第二种方案:用 hashMap 缓存遍历的过的节点

    还是头节点进行遍历,每一次遍历新的节点时,对比存储到 hashMap 集合是否有相同的节点,有,证明有环,无,存储到集合中

    伪代码:

    Node p = head
    HashMap hm = new HashMap()<Node,Node>
    while(p!=null){
        if(hm.get(p)){
            return true
        }
        hm.put(p,p)
        p =p.next
    }
    

    第三种方案:双指针遍历

    首先创建两个指针 1 和 2,同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针 1 每次向下移动一个节点,让指针 2 每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环

    伪代码:

    Node p = head
    Node q = head.next
    while(p!==q){
        if(p.next==null) return false
        p =p.next
        if(q.next==null) return false
        if(q.next.next==null) return false  
        q = q.next.next
    }
    return true
    

    此方案的时间复杂度为 O(n),空间复杂度为 O(1)

    作者简介

    考拉后端开发小哥 Rowland,热爱运动还有点萌!

    11 条回复    2019-05-20 16:12:46 +08:00
    Vegetable
        1
    Vegetable  
       2019-05-19 16:45:49 +08:00
    这...Leetcode 搬运工吗...
    JohnChiu
        2
    JohnChiu  
       2019-05-19 16:46:54 +08:00   ❤️ 2
    把 v2 当 csdn 了?
    helica
        3
    helica  
       2019-05-19 16:48:58 +08:00 via iPhone
    棒棒
    coffeSlider
        4
    coffeSlider  
       2019-05-19 16:53:29 +08:00 via Android
    帮楼主延伸一下,如何判断环的入口节点呢?
    yhxx
        5
    yhxx  
       2019-05-19 17:13:33 +08:00
    还以为是网易考拉。。。正准备看看是谁发的然后去嘲讽一下
    poplar50
        6
    poplar50  
       2019-05-19 17:27:08 +08:00 via Android
    来来再升级一下问题 找到两个链表的交点? ps: 链表可能有环
    Cbdy
        7
    Cbdy  
       2019-05-19 17:30:07 +08:00 via Android
    找本数据结构书看看吧,别一天到晚发这种帖子
    cxtrinityy
        8
    cxtrinityy  
       2019-05-19 17:51:53 +08:00 via Android
    就是有向图检测环吧,深度优先就可以做
    lizhuoli
        9
    lizhuoli  
       2019-05-19 20:29:39 +08:00 via iPhone
    这种无聊题怎么都搬上来了???
    taotaodaddy
        10
    taotaodaddy  
       2019-05-19 21:37:27 +08:00 via Android
    还可以升级一下:求一个链表中的环数
    chaplinj
        11
    chaplinj  
       2019-05-20 16:12:46 +08:00
    一句话就解决的事情
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2423 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 16:08 · PVG 00:08 · LAX 09:08 · JFK 12:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.