文档章节

Java判断链表是否有环的两种实现方法

孟飞阳
 孟飞阳
发布于 2016/06/17 10:19
字数 300
阅读 1812
收藏 0
package demo6;

import java.util.HashMap;

import demo6.LinkReverse2.Node;


/**
 * 判断链表是否有环的方法
 * @author mengfeiyang
 *
 */
public class LinkLoop {
	
	public static boolean hasLoop(Node n){
		//定义两个指针tmp1,tmp2
		Node tmp1 = n;
		Node tmp2 = n.next;
		
		while(tmp2!=null){
			tmp1 = tmp1.next;  //每次迭代时,指针1走一步,指针2走两步
			tmp2 = tmp2.next.next;
			if(tmp2 == null)return false;//不存在环时,退出
			int d1 = tmp1.val;
			int d2 = tmp2.val;
			if(d1 == d2)return true;//当两个指针重逢时,说明存在环,否则不存在。
			
		}
		return true; //如果tmp2为null,说明元素只有一个,也可以说明是存在环
	}
	
	//方法2:将每次走过的节点保存到hash表中,如果节点在hash表中,则表示存在环
	public static boolean hasLoop2(Node n){
		Node temp1 = n;
		HashMap<Node,Node> ns = new HashMap<Node,Node>();
		while(n!=null){
			if(ns.get(temp1)!=null)return true;
			else ns.put(temp1, temp1);
			temp1 = temp1.next;
			if(temp1 == null)return false;
		}
		return true;
	}
	
	public static void main(String[] args) {
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		n5.next = n1;  //构造一个带环的链表,去除此句表示不带环
		
		System.out.println(hasLoop(n1));
		System.out.println(hasLoop2(n1));
	}
}
执行结果:
true
true

 

© 著作权归作者所有

孟飞阳
粉丝 217
博文 1056
码字总数 566359
作品 5
朝阳
个人站长
私信 提问
[LintCode] Linked List Cycle(带环链表)

描述 给定一个链表,判断它是否有环。 样例 给出 -21->10->4->5, tail connects to node index 1,返回 true。 这里解释下,题目的意思,在英文原题中,tail connects to node index 1 表示的...

honeymose
2018/12/16
32
0
分享一份非常强势的Android面试题

马上步入金九银十了,是时候看一些面试题去鹅厂了,接下来我将分享一些面试题,每天总结一点点,希望对大家有所帮助! ListView和RecyclerView区别 参考链接: blog.csdn.net/shu_lance/a… ...

codeGoogle
2018/08/23
0
0
LeetCode 141:环形链表 Linked List Cycle

给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 是 ,则在该链表中没有环。 Given a linked list, det...

iCodeBugs
07/16
21
0
Java语言基础+计算机网络+数据结构 知识手册

最近有不少Java同学陆续开始准备找工作,这篇文章算是推给他们让他们提前准备一下。 加油,美好的一天开始啦~ 纯Java语言基础内容 1、常见集合源码分析。(以下是我们被问到过,能想起的所有...

MDove
2018/08/02
0
0
LeetCode:Valid Parentheses - 合理的括号搭配

1、题目名称 Valid Parentheses(合理的括号搭配) 2、题目地址 https://leetcode.com/problems/valid-parentheses/ 3、题目内容 英文:Given a string containing just the characters , ,......

北风其凉
2015/11/08
345
0

没有更多内容

加载失败,请刷新页面

加载更多

框架和库的区别

框架和库的区别 框架:是一套完整的解决方案;对项目的侵入性较大,项目如果需要更换框架,则需要重新架构整个项目。 node 中的 express; 库(插件):提供某一个小功能,对项目的侵入性较小...

庭前云落
24分钟前
4
1
基于 Dawn 进行多工程管理

1. 简述 当一个项目中子工程较多时,就会面临「单仓库(Monorepo)」还是「多仓库(Multirepo)」管理的问题。当然两个方式各有优缺点,而我们选择多工程单 Repo 时,能够带来一些管理上的简...

阿里云官方博客
24分钟前
3
0
Joomla 4具有可自定义的HTML电子邮件模板

Joomla 4大约每个月都会发布一个Alpha版本。上个月,我们得到了一个新的管理模板。 Joomla 4的最新版本是Alpha 12。 该版本的主要新特性是可定制的电子邮件模板。您将能够控制从您的网站发送...

六艺网络专注于Joomla
28分钟前
4
0
Idea配置

配置文件idea64.exe.vmoptions -Xms128m, 16 G 内存的机器可尝试设置为 -Xms512m (设置初始的内存数,增加该值可以提高 Java 程序的启动速度。 ) -Xmx750m, 16 G 内存的机器可尝试设置为 ...

行者终成事
30分钟前
5
0
大小仅1MB!超轻量级的人脸识别模型火爆Github

项目地址:https://github.com/Linzaer/Ultra-Light-Fast-Generic-Face-Detector-1MB 近日,用户Linzaer在Github上开源了一款适用于边缘计算设备、移动端设备以及 PC 的超轻量级通用人脸检测...

编程资源库
31分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部