数据结构和算法-判断单链表是否有环 求环的入口地址(java)

硅谷探秘者 10477 0 0

问题:如上图的一个链表,如何判断一个链表中是否存在环,以及如何求出环的入口以及何如求出链表的长度。

方案一:利用hash表

        首先准备一个hash表如hashMap等,然后从链表头部遍历链表,每次遍历一个节点先判断hashMap中是否存在这个节点,如果不存在就把这个节点放入hashMap中,如果存在证明这个链表是存在环的,并且这个节点就是环的入口。这个应该很好理解,也很好实现。当然这也是方案之一,也是很容易被想到的一种方法。因为使用了hash表,所以时间复杂度基本可以看作为O(n),因为每次遍历节点都要向hashMap中添加数据,所以空间复杂度也为O(n)。因为这种方法比较简单,所以不再贴出代码案例,下面重点分析一下下面的一种方法(快慢指针法),它的时间复杂度为O(n),但是空间复杂度可以降到O(1)。

方案二:快慢指针法

1.判断链表是否有环 

        算法流程:所谓的快慢指针就是有两个指针,初始都指向链的表头部,然后算法开始时慢指针一次向前移动一个节点,快指针一次向前移动两个节点。每次移动后判断两个指针是否指向同一个节点。如果是则说明该表链存在环。如果不是则继续上述操作移动指针,直到慢指针遍历完整个链表,则说明该链表没有环。

        证明:慢指针slow=slow->next;快指针fast=fast->next->next;进入链表后快指针一定在慢指针前面,如果链表有环,则二者一定会在环上相遇,(就像两个人在操场跑步,跑的快的一定会在某个地方和跑的慢的相遇)并且会在slow指针绕环走完第一圈之前相遇,因为slow每向前一步,fast向前两步,这表明经过这样一次操作两者距离就缩短1。而且经过多次操作以后两者的距离会逐渐缩小是(…4,3,2,1,相遇)又因为在同一个环中fast和slow之间的距离不会大于换的长度,因此到二者相遇的时候slow一定还没有走完一周(或刚好走完一周)。

2.找出环的入口

        从判断链表中是否有环的证明中可以得知当fast和slow相遇时,slow还没有走完链表一周,假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步,则fast走了2s步,又由于fast走过的步数也等于s + n*r(设环的长度为r)则:
(1)2*s = s + n * r
(2)s = n*r
如果假设整个链表的长度是L,入口和相遇点的距离是x,起点到入口点的距离是a,则更具第二步有:
(3)a + x = s = n * r
把n*r换成(n - 1) * r + r后得:
(4)a + x = (n - 1) * r + r
又因为链表的长度(L)=环的长度(r)+头结点到环的入口地址的长度(a),所以r=L-a替换(4)式中的r得:
(5)a + x =(n - 1) * r + (L - a)
(6)a= (n - 1) * r + (L -a -x)
暂且忽略(n - 1) * r
(6)式中得L -a –x正是两个指针第一次相遇时得节点到环得入口节点得距离。它和链表头头节点到环的入口节点的距离相等。
        因此我们可以在两指针相遇时将快指针重新指向链表的头指针,然后让他和慢指针一样一次移动一个节点,当两个节点再次相遇的时候这个相遇时的节点就是环的入口。

3.求出环的长度

        找到环的入口地址以后,从环的入口地址向下遍历,直到回到环的入口,遍历的节点的个数就是环的长度;

4.求链表的长度

        头结点到环的入口节点的长度好求,在加上环的长度就是链表的长度。

java代码
package a;
/**
 * 	链表节点类
 * @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);
	}
}

 


评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构和算法 1172 /*** 节点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodenext; publicNode(intdata
数据结构与算法 7603 题目:下方两棵二叉树右方二叉树为左方二叉树子树例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 1810 胜利者,胜利者编号,以及出局者顺序。解决方案使用双向循测试m=9,n=5输出:517436928代码(c++描述)Node.h#pragmaonceclassNode{public: i
前端(h5) 2062 js字符串为整原文:https://www.jb51.net/article/144255.htm字符串str达整代码:if(!/^\d+$/.test(str
数据结构与算法 1955 思想把所需要排序分成两个集合,一个待排序集合,一个已排序集合,每次从未排序集合顺序或随机拿取一个,把它加到已排序集合使其序,直到未排序集合中被取走完,束案例
数据结构与算法 1724 prim(普里姆)出。对于任何一个,理解实现只一个方面,更重要要明白它应用范围或应用场景,最小生成树应用非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 2132 原文接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性(必学) (必学
数据结构与算法 2749 广度优先搜索(dfs、深搜)java实现-用邻接矩阵示图定点之间关系如下图:则用邻接矩阵示为: privatestaticintmap[][]={ {0,3,6
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1 2024-08  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript 加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。