首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：481567 时间限制：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
王清江唷_全网同名头像 王清江唷_全网同名 
function hasCycle(head) {
    // write code here
    for (let i = 0; i <= 10000; i++) {
        if (head == null) {
            return false;
        }
        head = head.next
    }
    return true;
}
链表长度是1到10000，我直接一直下一个，走到底都还在循环，说明有环（大聪明做法）
发表于 2023-03-22 15:26:24 回复(0)
Javascript
王鑫DreamFox头像 王鑫DreamFox
访问过可以设置成undefined
发表于 2022-07-13 13:19:33 回复(0)
Javascript
Five鱼头像 Five鱼
function hasCycle( head ) {
    // write code here
    try{
        JSON.stringify(head);
        returnfalse;
    }
    catch{
        returntrue;
    }
}
发表于 2022-03-30 19:54:25 回复(0)
Javascript
已注销头像 已注销 
function hasCycle( head ) {
    // write code here
    if(!head || !head.next) return false
    let low = head
    let fast = head
    while(fast&&fast.next){
        low = low.next
        fast = fast.next.next
        if(low == fast) return true
    }
    return false
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2022-03-22 21:30:52 回复(0)
Javascript
迷途小学生头像 迷途小学生
此题有两种解法：

1.我们可以遍历链表。当每遍历一个node就设计一个标记位，如果我们遍历的节点已经存在标记，那么证明有环。 

function hasCycle( head ) {
    let cur = head;
    while(cur) {
        if(cur.flag) {
            return true;
        }
        cur.flag = true;
        cur = cur.next;
    }
    return false;
}

2.我们可以使用经典的快慢指针解法。 

function hasCycle( head ) {
    let slow = head;
    let fast = head;
     
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
         
        if(slow === fast) {
            return true;
        }
    }
    return false;
}


发表于 2021-12-22 09:51:53 回复(0)
Javascript
菜鸡大作战头像 菜鸡大作战
function hasCycle( head ) {
    // write code here
    while(head) {
        if(!head.state) head.state = true
        else return true
        head = head.next
        
    }
    return false
}
// 每经过一个节点，做个记录，如果该节点已被记录过则直接返回true
发表于 2021-12-09 10:53:38 回复(0)
Javascript
美英头像 美英 
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
function hasCycle( head) {
    // write code here
    if(!head){//通过5个
        return false;
    }
    var list = [];
    while(head && head.next){
        //只return true ,可通过12个
        //改成如下，可全部通过
        if(list.indexOf(head)==-1){//不存在加入list
            list.push(head);
        }else{
            //存在则返回true，表示有环，即有重复
            return true;
        }
        head = head.next;
    }
    return false;
    
    
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2021-11-09 18:06:30 回复(0)
Javascript
牛客362805906号头像 牛客362805906号 
function hasCycle( head ) {
    var hash=new Set()
    var flag=false
    while(head!=null){
        hash.add(head)
        head=head.next
        if(hash.has(head)){
           flag=true
           break
        }
    }
    return flag
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2021-09-09 10:39:13 回复(0)
Javascript
しまざきせつな头像 しまざきせつな
每个节点添加一个计数属性，如果单链表遍历下去走回了一个计数过的点说明成环 
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
function hasCycle( head ) {
    // write code here
    let index = head
    while(index && index.next) {
        if (index.count === 1) {
            return true
        } else {
            index.count = 1
        }
        index = index.next
    }
    return false
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2021-09-03 17:49:56 回复(0)
Javascript
Tsundere_Map头像 Tsundere_Map 
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
function hasCycle( head ) {
    let hashMap = new Map();
    while(head !== null){
        if(hashMap.has(head)){
            return true
        }
        hashMap.set(head, 0);
        head = head.next
    }
    return false;
}
module.exports = {
    hasCycle : hasCycle
};

发表于 2021-07-21 14:37:14 回复(0)
JavaScript
龙生_joel头像 龙生_joel

方法二：哈希法

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程。

方法二：快慢指针

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即快了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，
我们定义两个指针，一快一满。
慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
 var hasCycle = function(head) {
    if (!head || !head.next) return false

    let fast = head.next, slow = head;

    while (fast !== slow) {
      if (!fast || !fast.next) return false

      fast = fast.next.next
      slow = slow.next
    }
    
    return true
};
发表于 2021-07-04 17:51:20 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function hasCycle( head ) {
    // write code here
    if(!head){
        return false;
    }
    var slow = head,
        fast = head;
    while(fast != null && fast.next != null){ //之所以要加fast.next != null，是因为避免链表只有一个点的时候，slow.next和fast.next.next都是空的
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

发表于 2021-04-12 22:52:54 回复(0)
JavaScript
别卷啦！头像 别卷啦！
1.给已通过的节点加标志位，遍历链表 当下一节点已经被标志时，证明链表中有环 空间复杂度O(n) 
function hasCycle( head ) {
    // write code here
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
}
2.快慢指针 
    if(!head||!head.next) return false
    let slow = head,fast = head
    while(fast.next &&fast.next.next ){
        fast = fast.next.next
        slow = slow.next
        if(fast == slow) return true
    }
    return false


编辑于 2020-12-14 12:00:26 回复(1)
JavaScript
曾柔-牛客分柔头像 曾柔-牛客分柔
js版，快慢指针，定义两个指针，快指针 和慢指针，快指针先走一步，然后判断快指针和慢指针是否会指向同一个节点， 是的话返回true 否的话返回false；

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
function hasCycle( head ) {
    // write code here
    if(head == null || head.next == null) {
        return false;
    }
    var l1 = head;
    var l2 = head;
    while(l2 && l2.next) {
//         定义慢指针
        l1 = l1.next
        l2 = l2.next.next
        if(l1 == l2) {
            return true;
        }
    }
    return false;
}
module.exports = {
    hasCycle : hasCycle
};
发表于 2020-11-08 20:52:50 回复(0)
JavaScript
一条不会挣扎的咸鱼🐟头像 一条不会挣扎的咸鱼🐟
弗洛伊德判圈算法优化-传送的乌龟。 
function hasCycle( head ) {
    // write code here
    let r = head;// 兔子
    let t = r;// 乌龟    
    let countLimit = 2; //移动上限
    let step = 0; // 移动步数
    while(r){
        r = r.next;
        if(r === t){ // 相遇
            return true;
        }
        if(++step === countLimit){ // 达到上限
            step = 0;//步数清零
            t = r; //传送乌龟
            countLimit *= 2;  //增加移动上限 --- 主要为了减少慢指针赋值。          
        }
    }
    return false;
}



发表于 2020-09-16 22:29:10 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
15条回答 47569浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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