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

weblog 256 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);
	}
}
猜你喜欢
数据结构与算法 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
前端(h5) 392 js字符串为整数法原文:https://www.jb51.net/article/144255.htm字符串str达整数:if(!/^\d+$/.test(str
工具 876 web项目为ajax异步请importjavax.servlet.http.HttpServletRequest;publicclassAjaxUtil
java虚拟机(jvm) 227 jmapjava虚拟机自带内存映像工具,我们可通过该工具配合不同参数来查看java虚拟机内存详细信息(如程序中出现对象数量占用内存大小等),通过虚拟机内存使用情况来定
java基础 730 asm生成for循语句法1.jar包2.原java文件packageclub.jiajia.test3;publicclassExamp4{ publicintmethod(inta
数据结构与算法 6032 题目:两棵二叉树右二叉树为左二叉树子树例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
目录