Java如何判断一个链表有环？ 它的入口节点是什么？

2021-07-16 12:25:51 浏览数 (44)

链表是常用的几种数据结构其中一个。链表结构可以充分利用计算机内存空间，实现灵动的内存动态管理。本篇文章将通过 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<count;i++){
            res1 =res1.next;
        }
        res2 = node;
        while (res1!=res2 && res1!=null && res2!=null){
            res1 = res1.next;
            res2 = res2.next;
        }
        return res1;
    }
}

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);

    }


}

main函数测试结果

以上就是用 Java 判断一个链表是否有环和确定它的入口节点是什么的详细内容，想要了解更多 java 数据结构的相关资料请关注W3Cschool其它相关文章！


Java

2 人点赞