如何确定一个链表有环,入口节点是什么?
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函数测试;
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://zxbcw.cn/post/209134/
- 转载请注明:必须在正文中标注并保留原文链接
- QQ群: PHP高手阵营官方总群(344148542)
- QQ群: Yii2.0开发(304864863)