Java怎么判断一个链表有环

这篇文章主要介绍了Java怎么判断一个链表有环，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

链表是常用的几种数据结构其中一个。链表结构可以充分利用计算机内存空间，实现灵动的内存动态管理。本篇文章将通过 Java 代码展示为大家介绍如何判断一个链表是个有环链表，以及有环链表的入口点。

1.首先定义一个单链表；

var ，next,是单链表中的属性，分别表示节点值和下一个节点的指向；
代码如下：

//定义一个链表  class  List{    public  int var;    public  List next;//有参构造    public List(int var) {        this.var = var;    }//无参构造    public List() {    }    //创建一个带环的链表    public  List Create(){        List a = new List(1);        List b = new List(2);        List c = new List(3);        List d = new List(4);        List e = new List(5);        List f = new List(6);        a.next = b;        b.next =c;        c.next = d;        d.next =e;        e.next = f;        f.next =d;        return  a;    }

2.编写判断是否存在环

如果存在，则返回这个节点，如果不存在则返回null,定义快慢指针，如果快的追上了慢的指针，那么这个链表必存在环，如果没有追上，或者都为null，那么这个链表没有环；
代码如下：

//判断是否有环，并找到相遇的节点public  List MeetingNode(List node){    List slow = new List();    List fast = new List();    if(node==null) return  null;    slow = node.next;    if(slow==null) return  null;    fast=slow.next;    while (fast!=null && slow!=null){        if (fast==slow){            return fast; //fast追上了slow，确定是一个有环的链表；        }        slow = slow.next;        fast = fast.next;        if(fast!=null){            fast = fast.next;        }    }   return null;}

3.寻找入口节点

先让快指针先走环的节点的个数步，在让慢指针开始走，如果两个指针相遇的话，那么相遇的节点必然是环的入口节点
代码如下：

  public  List Enterdear(List node){        if(node==null) return null;        if(MeetingNode(node)==null) return null;        int count =1;        List res2;        List res1 = MeetingNode(node);        while (res1.next!=MeetingNode(node)){            res1 = res1.next;            count++;        }        res1 = node;        for(int i = 0;i
main函数测试；
public class Deom {    public static void main(String[] args) {       List SB = new List();       List res = SB.Create();       List dear= SB.Enterdear(res);       System.out.println(dear.var);    }}
感谢你能够认真阅读完这篇文章，希望小编分享的"Java怎么判断一个链表有环"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!