好得很程序员自学网

<tfoot draggable='sEl'></tfoot>

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链表及入口节点的资料请关注其它相关文章!

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

查看更多关于java如何确定一个链表有环及入口节点的详细内容...

  阅读:17次