个人中心
gpt4 book ai didi

java如何确定一个链表有环及入口节点

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 34 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java如何确定一个链表有环及入口节点由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

如何确定一个链表有环，入口节点是什么？

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

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//定义一个链表
   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，那么这个链表没有环； 代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//判断是否有环，并找到相遇的节点
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.寻找入口节点

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   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函数测试； 。

?
1
2
3
4
5
6
7
8
9
10
11
12
ublic 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如何确定一个链表有环及入口节点

以上就是java如何确定一个链表有环及入口节点的详细内容，更多关于java链表及入口节点的资料请关注我其它相关文章！ 。

原文链接：https://blog.csdn.net/ILOVEMYDEAR/article/details/115474750 。

最后此篇关于java如何确定一个链表有环及入口节点的文章就讲到这里了,如果你想了解更多关于java如何确定一个链表有环及入口节点的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

34 4 0
文章推荐： 如何在 Microsoft SQL Server 上恢复 SA 密码
文章推荐： 《Linux 内核编码风格》官方手册最新中译本
文章推荐： 浅谈javap命令拆解字节码文件
文章推荐： 开发环境下如何进行安全加固呢
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com