首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：483551 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客576944030号头像 牛客576944030号
java的给我看笑了哈哈
编辑于 2024-03-08 15:36:31 回复(0)
Java
hi_wassuh头像 hi_wassuh 
import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        if(head==null){
            return false;
        }
        while(fast!=null&&fast.next!=null){  //如果没环的话快指针会先到链表尾
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

发表于 2023-10-11 14:11:51 回复(0)
Java
练习时长两年半的太平湖水怪很理智头像 练习时长两年半的太平湖水怪很理智
只想说，这个题目表述真的太垃圾！读半天没读明白！直接简单写判断链表是否有环不就完了？说了一堆废话。而且这个题有bug 
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = null;
        while ((input = br.readLine()) != null) {
            String[] ss = input.split("}");
            int last = Integer.parseInt(ss[1].split(",")[1]);
            System.out.println(last != -1);
        }
    }
}

发表于 2023-09-22 18:45:36 回复(0)
Java
@唯时头像 @唯时 
public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast)
            return true;
    }
    return false;
}

发表于 2023-09-06 17:14:52 回复(0)
Java
要讲武德🖐🏻头像 要讲武德🖐🏻
public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head != null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
发表于 2023-08-10 16:17:27 回复(0)
Java
牛客101757813号头像 牛客101757813号 
public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            if(list.contains(head)){
                return true;
            }
            list.add(head);
            head = head.next;
        }
        return false;
    }

发表于 2023-08-03 10:55:46 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public boolean hasCycle(ListNode head) {
        //找环，快慢指针  终将相遇
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }

发表于 2023-07-17 19:23:29 回复(0)
Java
北极的小神龙头像 北极的小神龙 
import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        if (head.val == 100001) {
            return true;
        }
        head.val = 100001;
        return hasCycle(head.next);
    }
}
看评论学到了快慢指针，我用了下规则中|val| < 100000。如果再次遇到100001说明有换。
发表于 2023-07-11 08:07:50 回复(0)
Java
在求职的小确幸很内向头像 在求职的小确幸很内向
判断给定的链表中是否有环。如果有环则返回true，否则返回false。用Java写代码回复我
gpt3.5:
以下是Java代码实现： 
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false; }
    ListNode slow = head; ListNode fast = head.next; while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false; } slow = slow.next; fast = fast.next.next; }
    return true; }

其中，ListNode是链表节点的定义，包含一个val属性和一个next属性，表示节点的值和下一个节点的指针。具体代码实现中，我们使用快慢指针的方法来判断链表是否有环。我们让一个指针slow每次移动一步，另一个指针fast每次移动两步，如果链表有环，那么fast指针最终会追上slow指针，从而形成一个循环。如果fast指针走到了链表的末尾，那么说明链表没有环。

发表于 2023-06-09 14:34:08 回复(1)
Java
进入人才池头像 进入人才池 
public class Solution {
    public boolean hasCycle(ListNode head) {
        int x = (int)1e5+1;
        while ( head != null ) {
            if ( head.val == x ) return true;
            head.val = x;
            head = head.next;
        }
        return false;
    }
}

发表于 2023-04-29 14:59:19 回复(0)
Java
超级无敌霸王龙头像 超级无敌霸王龙
利用java的面对对象特性求题解, 遍历链表同时, 将每个节点存入list, 拿到当前节点时, 先判断list中是否包含此节点 , 如包含 , 则有环, 方法直接返回true .
遍历完链表则代表没有环,返回false . 核心是利用对象的唯一性进行比对; 
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        ArrayList<ListNode> list = new  ArrayList<ListNode>();
        while(head!=null){
            if(list.contains(head)){
                return true;
            }
            list.add(head);
            head = head.next;
        }
        return false;
    }
}

发表于 2023-02-28 13:53:16 回复(2)
Java
Hitofuncy头像 Hitofuncy
不要想象得那么复杂，直接用hashCode + set也行。 
import java.util.HashSet;
public class Solution {
    public boolean hasCycle(ListNode head) {
           
        HashSet<Integer> vals_hash = new HashSet<>();
        for(ListNode tmp = head;tmp != null;tmp = tmp.next){
            if(vals_hash.contains(tmp.hashCode())){
                return true;
            }
            vals_hash.add(tmp.hashCode());
       }
       return false;
    }
}


发表于 2022-12-22 16:28:28 回复(1)
Java
宝峰201811130926571头像 宝峰201811130926571 
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

发表于 2022-11-22 20:27:47 回复(0)
Java
牛客341319853号头像 牛客341319853号 
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast2 = head;
        ListNode fast3 = head;//增加超快指针，防止路途中慢指针与快指针遇不上
        while(fast3 != null && fast3.next != null && fast3.next.next != null){
            fast3 = fast3.next.next.next;
            fast2 = fast2.next.next;
            slow = slow.next;
            if (slow == fast2 || slow == fast3) {
                return true;
            }
        }
        return false;
    }
}


发表于 2022-11-05 11:16:09 回复(0)
Java
624huiguorou头像 624huiguorou
有环链表的模板

a和b都指向head（无法使用a和b的while判断），b!=null和b.next!=null（不到尽头，并且可以相等就是有环），就在里面走，a=a.next;和b=b.next.next;（因为有b.next.next，所以b.next不能为空。而又因为有b.next，所以b不能为空。这两种情况都会发生） 

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //有环,a和b都在head，a一次走一个，b一次走两个
    //b!=null和b.next!=null就一直走（有环的模板）
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode a = head, b = head;
        //可以理解为b.next.next，b.next不能为空。而b.next，则b不能为空
        //由于连续走两下，所以b可能会为空
        while(b != null && b.next != null){
            a = a.next;
            b = b.next.next;
            if(a == b) return true;
        }
        return false;
    }
}

10个线程顺序打印1-10 
package com.ssy.test;

public class MultiThreadSequencePrint{

    //需要打印的数字
    private int N;

    //线程总数
    private int mc;

    //当前打印到的数字
    private volatile int VC;

    private class PrintRunnable implements Runnable{

        private final int NUMBER;

        public PrintRunnable(int number) {
            this.NUMBER = number;
        }

        @Override
        public void run() {
            //while循环保证线程处于执行状态，获取CPU时间
            while (true){
                //如果不是自己执行打印，自旋等待
                //因为每次读取VC时都需要读取最新的值，所以VC为volatile修饰
                while (VC % mc != NUMBER){//自旋
                    //自旋过程中发现已经打印到N，则结束线程
                    if (VC > N){
                        return;
                    }
                }
                //确定需要自己打印，获取内置锁
                synchronized (MultiThreadSequencePrint.class){
                //二次判断，如果已经打印到N，结束线程
                if (VC > N){
                    break;
                }
                //打印，并且更新VC
                System.out.println(Thread.currentThread().getName() + " " + VC);
                VC++;
                }
            }
        }
    }

    //函数初始化mc个线程，并且启动所有的线程
    public void printSeqNum(int N, int mc){
        this.N = N;
        this.mc = mc;
        this.VC = 1;
        for (int i = 0; i < mc; ++i){
            new Thread(new PrintRunnable(i)).start();
        }
    }

    //main函数作为测试用例
    public static void main(String[] args){
        MultiThreadSequencePrint o = new MultiThreadSequencePrint();
        o.printSeqNum(10, 10);
    }

}




发表于 2022-10-26 11:12:03 回复(0)
Java
dynamo1头像 dynamo1 
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return false;
        }
        //快慢指针法
        ListNode quicker = head.next.next;
        ListNode slow = head;

        while(quicker != null && quicker.next != null) {
            if (quicker == slow) {
                return true;
            }
            quicker = quicker.next.next;
            slow = slow.next;
        }
        return false; 
    }
}

发表于 2022-10-16 15:59:00 回复(0)
Java
程序猿找工作头像 程序猿找工作 
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
       
        while(head!=null){
            if(head.val==Integer.MIN_VALUE){
                return true;
            }
            head.val = Integer.MIN_VALUE;
            head = head.next;
        }
        return false;
    }
}

发表于 2022-10-03 10:42:48 回复(0)
Java
牛客用户007头像 牛客用户007
留下足迹 
import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }

        return false;
    }
}

发表于 2022-08-18 19:02:46 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
103条回答 47624浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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