如何确定一个链表有环,入口节点是什么?
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