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.寻找入口节点

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

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

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

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

相关文章

快网idc优惠网

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

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

2.编写判断是否存在环

3.寻找入口节点

相关文章

微信

快网idc优惠网

QQ交流群