用Java实现判断链表是否有环，环的大小，环的长度以及计算链表的长度

今天药忘吃喽~ 2022-06-10 13:21 235阅读 0赞

public static void main(String\[\] args) \{  
Node list = new Node();  
Node top = list;  
list.n=1;  
for(int i = 2;i < 10; i++)\{  
//list的next指向一个新的Node  
list.next = new Node();  
//新的Node的n赋值为i  
list.next.n=i;  
//list指向新的Node  
list = list.next;  
\}  
list.next = top.next.next.next;  
list=top; //让list回到起点，指向头结点  
//1.判断有没有环  
Node list1 = top;//都至于起点即根节点   慢  
Node list2 = top;  //快  
//思想：两个数同时跑，如果相遇，即是有环  
boolean flag=false;  
for(;(!(list1==list2))||(list1==list2&&list1==top);)\{  
System.out.println("进入循环了");  
if(list1==null||list1.next==null)\{  
flag=true;  
break;  
\}  
list1=list1.next;  
list2=list2.next.next;  
System.out.println(list1.n + ":" + list2.n);  
\}  
if(flag==true)\{  
System.out.println("此链表没有环");  
\}else if(flag==false)\{  
System.out.println("此链表有环");  
\}  
  
  
//2.环的大小是多少？让他俩在相遇点一起跑，再次相遇慢的跑的举例即是环的长度  
int count=0;  
for(;;)\{  
list1=list1.next;  
list2=list2.next.next;  
count++;  
if(list1==list2)\{  
break;  
\}  
\}  
System.out.println("环的长度是：" + count);  
  
//3环的切入点是多少？  
list1=top;  
for(;!(list1==list2);)\{  
list1=list1.next;  
list2=list2.next;  
\}  
System.out.println("环的切入点是"+list1.n);  
  
//4.链表的长度：  
list1=top;  
  
for(;!(list1==list2);)\{  
list1=list1.next;//将一个拉回节点  
count++;  
\}  
System.out.println("链表的长度为：" + count);  
\}  
  
  
\}  
//链表的节点：  
class Node\{  
int n;  
Node next;  
\}