链表问题--如何判断链表有环?
发布于 1 个月前 作者 kalengo 663 次浏览 来自 分享

一、题目描述

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

二、解题思路

方案一:暴力法

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

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)

5 回复

DFS的遍历, 找到重复节点路径

第三种方案:双指针遍历 啥意思, 没看懂…

@pengliheng 打个比方,两个人跑步,一个跑得飞快,另一个跑得很慢,如果是跑直线,那么两个人再也不会相遇,但如果是跑环形路线,那跑得快的人必将会跑到慢的人后面,然后追上

@zengming00 还是老鸟解读犀利👍

回到顶部