判断单链表是否有环以及求环的入口和环长度2种方案分析-附java代码

weblog 885 0 0
/**
 * 	链表节点类
 * @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);
	}
}
猜你喜欢
数据结构与算法 9720 问题:如上图一个,如何一个存在如何何如一:利用hash首先准备一个hash如hashMap等,然后从头部遍历,每次遍历一个
数据结构与算法 1057 胜利者,胜利者编号,出局者顺序。解决使用双向循测试数据m=9,n=5输出:517436928(c++描述)Node.h#pragmaonceclassNode{public: i
weblog 1049 java浏览器类型ie浏览器importjavax.servlet.http.HttpServletRequest;/*** 浏览器类型*@author硅谷探秘者(jia
前端(h5) 1195 js字符串为整数法原文:https://www.jb51.net/article/144255.htm字符串str达整数:if(!/^\d+$/.test(str
mqtt协议 658 示数据包大小最大值256M。  对剩余字段编解,可理解为128进制运算。如果低位字节满128,则向高位字节进1。那么进位系数就128。  下面用一段描述对剩余字段计算
工具 1503 web项目为ajax异步请importjavax.servlet.http.HttpServletRequest;publicclassAjaxUtil
java基础 3062 至执行完毕过程,就对应着一个栈帧在虚拟机栈中从栈到出栈过程。  经常人把Java内存区域笼统地划为堆内存(Heap)栈内存(Stack),这式直接继承自传统C、C++程序内存布
mqtt协议 549 传输,开销很小(固定头部2字节),协议交换最小化,降低网络流量。这就为什么在介绍里说它非常适合”在物联网领域,传感器与服务器通信,信息收集”,要知道嵌式设备运算能力带宽都相对薄弱
目录