首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：508466 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
判断给定的链表中是否有环。如果有环则返回true，否则返回false。


数据范围：链表长度 ，链表中任意节点的值满足
要求：空间复杂度 ，时间复杂度

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
示例1

输入

{3,2,0,-4},1

输出

true

说明

第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2

输入

{1},-1

输出

false

说明

第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3

输入

{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

输出

true

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
JavaScript Node
希望学好英语的小镇做题家头像 希望学好英语的小镇做题家
快慢指针法 
function hasCycle(head) {
    let fast = head, slow = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
}


发表于 2022-10-17 15:41:21 回复(0)
JavaScript Node
自闭文文头像 自闭文文 
function hasCycle( head ) {
    // write code here
    // 有环就会再次遇到
    while (head != null) {
        if (head.val == Infinity) {
            return true;
        } 
        head.val = Infinity;
        head = head.next;
    }
    return false;
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2022-10-03 19:55:58 回复(0)
JavaScript Node
337845818头像 337845818 
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
function hasCycle(head) {
    // write code here
    if (!head) {
        return false
    }
    let fast = head
    let slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast == slow) {
            return true
        }
    }
    return false
}

module.exports = {
    hasCycle: hasCycle
};

发表于 2022-09-02 21:02:22 回复(0)
JavaScript Node
载梦覆星河头像 载梦覆星河 
function hasCycle( head ) {
    // write code here
    if (head== null) {
        return false
    }
//     双指针 快慢指针
    var slow = head
    var fast = head
    while(slow!=null && fast.next!=null) {
        slow = slow.next
        fast = fast.next.next
        //     当双指针相遇，即代表指针有环
        if(slow == fast) {
            return true
        } 
    }
    return false
}
module.exports = {
    hasCycle : hasCycle
};
发表于 2022-05-23 16:49:25 回复(1)
JavaScript Node
嘉然今天恰烧烤头像 嘉然今天恰烧烤 
function hasCycle( head ) {
    // write code here
    let tmpArray = []
    while(head != null) {
        if(tmpArray.indexOf(head.next) !== -1) return true
        if(head.next !== null) tmpArray.push(head.next)
        head = head.next
    }
    return false
}

发表于 2021-12-08 20:03:55 回复(0)
JavaScript Node
StarChaser_Z头像 StarChaser_Z 
function hasCycle( head ) {
    // write code here
    const circleSet = new Set()
    while(head){
        if(circleSet.has(head))
            return true
        circleSet.add(head)
        head = head.next
    }
    return false
    
}
module.exports = {
    hasCycle : hasCycle
};
这道题一开始没理解什么意思，网上搜了一下就懂了
利用js的set就可以很完美的解决这一道题，相信不用解释大家也能看得懂
发表于 2021-09-25 17:41:33 回复(0)
JavaScript Node
周欣仪头像 周欣仪
根据大佬们的题解，判断一个链表是否有环，有两种解决方案。
    1.利用快慢指针来对链表进行遍历，一个slow指针走一步，一个fast指针走两步，如果相遇，那么说明有环。
js代码如下所示： 
function hasCycle( head ) {
    // write code here
    //定义两个快慢指针
    if(head==null)
        {
            return false
        }
    var slow=head
    var fast=head
    while(fast!=null && fast.next!=null)
        {
            slow=slow.next
            fast=fast.next.next
            if(slow==fast)
                {
                    return true
                }
        }
                 return false
}
   
 2.利用哈希表来存储遍历过的链表节点，如果节点在哈希表中不存在，就将节点存储到哈希表中，如果继续遍历，哈希表中有遍历的节点，那么链表一定有环。
js代码如下所示： 
function hasCycle( head ) {
    // write code here
    if(head==null)
        {
            return false
        }
    var temp=head
    //定义一个set用来存储数据
    var set=new Set()
    //结束条件是节点为空
    while(temp!=null)
        {
            if(set.has(temp))
        {
            return true
        }
            else{
        set.add(temp)
                }
        temp=temp.next
        }
    return false
}


发表于 2021-08-19 10:07:43 回复(1)
JavaScript Node
扭扭会更好吃头像 扭扭会更好吃
//使用set
function hasCycle( head ) {
    var set = new Set()
    while(head!=null){
        if(set.has(head)){
            return true
        }else{
            set.add(head)
        }
        head = head.next
    }// write code here
    return false
}
module.exports = {
    hasCycle : hasCycle
};
发表于 2021-08-06 19:35:32 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
9条回答 49167浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断链表中是否有环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号