[数据结构与算法] 如何判断单链表是否有环

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 如何判断单链表是否有环 -> 正文阅读

[数据结构与算法]如何判断单链表是否有环

在这里插入图片描述

节点类

@Data
public class Node {
    /**
     * 用于保存节点中的数据
     */
    private Object data;
    /**
     * 用于保存下一个节点的地址值
     */
    private Node next;

    public Node(Object data) {
        this.data = data;
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

实现类

package day04;

/**
 * @Author yqq
 * @Date 2022/05/08 16:57
 * @Version 1.0
 */
public class Test05 {
    public static void main(String[] args) {
        //创建一个单链表
        Node lastNode = new Node(55);
        Node node4 = new Node(44,lastNode);
        Node node3 = new Node(33,node4);
        Node node2 = new Node(22,node3);
        Node headNode = new Node(11,node2);
        lastNode.setNext(node3);
        //测试单链表是否有环
        boolean flag = isCycle(headNode);
        System.out.println(flag);
    }

    /**
     * 判断单链表是否有环
     * @param headNode 首节点
     * @return
     */
    public static boolean isCycle(Node headNode){
        //处理headNode为null的情况
        if (headNode == null)
            return false;
        //定义一个快指针，每次往后走两步
        Node fast = headNode;
        //定义一个慢指针，每次往后走一步
        Node slow = headNode;
        //定义一个循环，用于判断单链表是否有环
        while (fast != null && fast.getNext() != null){
            //设置快指针和慢指针每次往后移动
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            //如果fast和slow指向的是同一个节点，则证明单链表有环
            if (fast == slow)
                return true;
        }
        //执行到此处，证明单链表是无环单链表
        return false;
    }
}