本站发布的所有文件/源码/文档/软件等均提供免费下载。
但本站带宽较低、流量有限,为防止恶意下载、盗刷流量,所以只能登陆网站后才能下载!
若给您带来不便请见谅~
为了方便,您可以通过qq授权登陆,也可以通过钉钉授权登陆。也可以通过邮箱注册后登陆。
判断单链表是否有环以及求环的入口和环长度2种方案分析-附java代码
/**
* 链表节点类
* @author 硅谷探秘者(jia)
*/
class Node{
public int data;
public Node next;
public Node(int data) {
this.data=data;
}
public Node(Node next,int data) {
this.data=data;
this.next=next;
}
}
public class A3 {
public static void main(String[] args) {
/**
* 构造链表 15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->8
*/
Node n1=new Node(1);
Node n2=new Node(n1,2);
Node n3=new Node(n2,3);
Node n4=new Node(n3,4);
Node n5=new Node(n4,5);
Node n6=new Node(n5,6);
Node n7=new Node(n6,7);
Node n8=new Node(n7,8);
Node n9=new Node(n8,9);
Node n10=new Node(n9,10);
Node n11=new Node(n10,11);
Node n12=new Node(n11,12);
Node n13=new Node(n12,13);
Node n14=new Node(n13,14);
Node n15=new Node(n14,15);
n1.next=n10;
Node e=cycles(n15);
if(e!=null) {
System.out.println("入口地址:"+e.data);
int length=length(e,e);
int length2=lengthX(n15,e);
System.out.println("环的长度:"+length);
System.out.println("链表长度:"+(length+length2));
}else {
System.out.println("没有成环");
}
}
/**
* 判断链表是否成环,是返回环的入口节点,否则返回null
* @param n
* @return
*/
public static Node cycles(Node n) {
if(n.next!=null&&n.next.next!=null) {
Node slow = cycle(n.next,n.next.next);
if(slow!=null)
return entrance(n,slow);
else
return null;
}else {
return null;
}
}
/**
* 递归判断是否成环
* @param slow 慢指针
* @param fast 快指针
* @return
*/
public static Node cycle(Node slow,Node fast) {
if(fast==null)
return null;
else
if(slow==fast)
return slow;
else
if(fast.next!=null&&fast.next.next!=null)
return cycle(slow.next,fast.next.next);
else
return null;
}
/**
* 寻找入口地址
* @param slow
* @param fast
* @return
*/
public static Node entrance(Node slow,Node fast) {
if(slow==fast) return slow;
else return entrance(slow.next, fast.next);
}
/**
* 计算链表长度
* @param n
* @param e
* @return
*/
public static int length(Node n,Node e) {
n=n.next;
if(n==e) return 1;
else return 1+length(n, e);
}
/**
* 计算头节点到环的入口的长度
* @param n
* @param e
* @return
*/
public static int lengthX(Node n,Node e) {
if(n==e)
return 0;
else
return length(n, e);
}
}
猜你喜欢
数据结构与算法
8935
问题:如上图的一个链表,如何判断一个链表中是否存在环,以及如何求出环的入口以及何如求出链表的长度。方案一:利用hash表首先准备一个hash表如hashMap等,然后从链表头部遍历链表,每次遍历一个
数据结构与算法
217
胜利者,求胜利者的编号,以及出局者的顺序。解决方案使用双向循环链表测试数据m=9,n=5输出:517436928代码(c++描述)Node.h#pragmaonceclassNode{public: i
weblog
99
java判断请求的浏览器类型是否是ie浏览器importjavax.servlet.http.HttpServletRequest;/*** 浏览器类型判断*@author硅谷探秘者(jia
blog
js判断字符串是否为整数的方法
前端(h5)
392
js判断字符串是否为整数的方法原文:https://www.jb51.net/article/144255.htm判断字符串str是否为表达整数代码:if(!/^\d+$/.test(str
blog
web项目判断请求是否为ajax异步请求
工具
876
web项目判断请求是否为ajax异步请求importjavax.servlet.http.HttpServletRequest;publicclassAjaxUtil
java虚拟机(jvm)
227
jmap是java虚拟机自带的一种内存映像工具,我们可以通过该工具配合不同的参数来查看java虚拟机内存的详细信息(如程序中出现的所有对象的数量以及占用内存大小等),以及通过虚拟机内存的使用情况来定
blog
asm生成for循环语句方法
java基础
730
asm生成for循环语句方法1.jar包2.原java文件packageclub.jiajia.test3;publicclassExamp4{ publicintmethod(inta
数据结构与算法
6032
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5