java判断单链表是否有环

发布时间:2021-09-21 19:29:15

算法和数据结构是面试考核的重点,其中经常问到单链表的问题,比如单链表的逆置、判断单链表是否有环等问题,这些主要考察的程序员的基本代码能力,今天给大家一起学*一下如何判断单链表是否有环。


那么如何判断一个单链表是否有环呢?(这个好像是谷歌的面试题目)先说一下算法思想:


我们可以设置两个指针分别叫做slow和fast,遍历这个链表,其中让slow指针每次走一步,而fast指针则每次走两步。大家想一下,如果链表有环会出现什么情况,链表有环肯定在某一个时刻这两个指针会指向同一个节点,也就是说如果出现slow.data == fast.data表示链表有环(前提是这个链表的各个节点的数据域都不相同);那么什么情况下是没有环的呢?链表如果没有环那么fast指针会先到达链表的末尾,此时链表肯定是不存在环的。算法的思路很简单,下面给出具体的代码实现:?


package cn.cqupt.linked;

public class CheckLinkLoop {
private static class Node{
private int data;
private Node next;

Node(){}
Node(int data){
this.data = data;
this.next = null;
}
Node(int data,Node next){
this.data = data;
this.next = next;
}
}

public static boolean isLoop(Node head){
Node slow = head.next;
Node fast = head.next.next;

// 链表为空或者只有一个节点
if(slow == null || fast == null){
return false;
}
while(slow.next != null){

// 只有 两个节点,当然是不存在循环的
if(fast.next == null){
return false;
}
// 如果slow的数据域和fast的数据域相同,则表示有环
if(slow.data == fast.data){
return true;
}
// slow指针走一步,fast走两步
slow = slow.next;
fast = fast.next.next;

//如果fast走到最后为空,表示没有环
if(fast == null){
return false;
}
}
return false;
}
public static void main(String[] args){
// 构造链表 1->2->3->4->5->6-4;
Node head = new Node();
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
Node e = new Node(5);
Node f = new Node(6);

head.next = a;
a.next = b;
b.next = c;
c.next = d;
d.next = e;
e.next = f;
f.next = d;
// 结果
System.out.println(isLoop(head));
}
}

?


?


?

相关文档

  • 高考复读生的录取和应届生有什么区别吗
  • 小学生暑假作文的精彩例文素材
  • 2018年中学德育工作计划
  • 未来20年内,无人驾驶将颠覆这33大行业
  • 公司3.15庆典活动主持词
  • 高考语文三轮复习古诗歌形象强化提升练习
  • 算法训练
  • 高中历史学习心得体会范文
  • 湖南公选考试公共管理知识强化题及答案
  • 高二学期政治教学工作总结
  • Nginx访问报域名解析失败
  • 大学生社会实践经历心得体会精选多篇
  • Git:同步他人的远程仓库至自己的Git服务器并自动定时更新
  • 电脑中了病毒的解决方法
  • 男人怎样健身计划
  • centos7.5部署rancher2
  • “大孩子”是我最理想的妈妈
  • 联通卡半年没用还可以补办吗
  • torch.cat 和 torch.stack的区别
  • 一次难忘的考试叙事作文600字
  • 大自然的名言大全
  • 培训班领导讲话精选多篇
  • 超级冷笑话脑筋急转弯大全及答案
  • 微单相机
  • linux远程终端执行命令,Linux终端登录远程主机SSH
  • 北京市大学生创业扶持政策
  • 2019妇产科医生个人工作总结
  • java小程序 适合初学者
  • 忘掉过去的说说 关于忘掉的说说45句
  • 参加结婚请假申请书怎么写
  • 猜你喜欢

  • 2013苏教版数学三下《面积单位间的进率》ppt课件1
  • 植物生理学5细胞及信号转导
  • 2019年国家注册一级消防工程师《消防安全技术综合能力》真题D卷 含答案
  • 武警总队医院内科医师地理教师个人述职报告范文与学*十八届五中全会精神心得体会范文精选3篇
  • 陈伟联《火柴天堂》歌词
  • 世界粮食日宣传活动方案_2
  • 培训专题-尽职调查服务协议
  • 青年志愿者协会招新的策划书
  • 保安每日巡查记录表(按此表格制作_每本页数30页)500本
  • 详细图解步骤win7系统安装
  • 2.8 字符集知识-让前端告别乱码
  • 在体验和感悟中成长
  • 六年级庆春节手抄报内容
  • 2019教育高考英语一轮复习课件(人教版必修1):《15Nelson Mandela—a modern hero》(100ppt)数学
  • 2019最新人教版小学语文二年级下册:鲁滨孙漂流记教案2-精品资料
  • 【2018最新】企业班组工作总结-范文word版 (9页)
  • (证明)单位工作证明标准范本
  • 如何提高小学信息技术的教学效率
  • 什么药物延时效果好
  • 华为账号登录密码忘了
  • 朋友结婚在国外去不了怎么办
  • 中国邮政集团公司山西省宁武县圪谬邮政支局企业信用报告-天眼查
  • 2020版一年级数学(下册)开学检测试卷 外研版A卷附答案
  • 浅谈农村留守学生心理问题的成因与对策
  • 泡脚养生助长寿 小心泡脚六禁忌
  • 【精编范文】201X年辽宁高考志愿填报时间以及批次设置-范文word版 (3页)
  • VS2013 下安装 Qt5
  • SqlServer 查看死锁的进程
  • 郑州振业广告信息有限公司企业信用报告-天眼查
  • 儿童口腔及视力保健知识讲座
  • 加强农村文化阵地建设,创新农村文化活动形式
  • 2019教育六年级上册英语课件Unit 7 I Had a Good TimeWhat did you do there陕旅版数学
  • 港版苹果xr支持电信卡吗
  • 精品学*七年级语文下册第三单元11台阶教学设计新人教版
  • 南财网络教育专升本成教--货币银行学课后*题及其答案
  • 铜川市大唐养生园开发建设有限公司企业信用报告-天眼查
  • 面具的设计制作教案初中美术人美版七年级上册.
  • 浅谈建筑施工测量的监理工作
  • damiani是什么牌子?damiani是奢侈品吗?
  • 总结参考-小学四年级工作总结4篇
  • 基于AT89S52单片机的简易智能小车的设计_廖天发
  • 仙游长旺古典家具有限公司企业信用报告-天眼查
  • 行政人事工作【流程图】)资料
  • 2014香港特别行政区会计证最新考试试题库
  • 餐饮品牌加盟商招商代理协议书范本-(优质文档)
  • 庆元旦作文900字
  • 丙肝弱阳性怎么回事
  • 洪山语文中考模拟试卷1
  • 河北省衡中清大教育集团高一上学期第五次月考(期末)英语试题
  • 中国梦我的梦
  • 舜风世纪花园智能小区一卡通系统工程案例
  • 昆明章吉商务信息咨询有限公司企业信用报告-天眼查
  • 【银得人生】2012年2月28日黄金、白银分析及操作建议
  • 心理测试交往性格题目
  • 初一作文:那年那月那泪光作文800字
  • 2011年深圳中考英语基础词汇表
  • 2014年安徽巢湖公务员面试培训,资格复审:全真模拟题3
  • 2018_2019版高中语文第三单元散文第12课鱼书课件粤教版
  • 大陆xxx公司员工辞职报告模板
  • 知识点一 雌性动物的生殖器官
  • 债权人建议债务人诈骗第三人的钱是否构成诈骗罪
  • 前台文员岗位职责_范文
  • 小学六年级上科学复*资料
  • 注册国际投资分析师卷一答案
  • 蟋蟀的饲养方法
  • 不是我吹是什么意思 不是我吹是什么梗
  • 劳动节的作文400字优质8篇
  • 【英语词汇】赵丽词汇笔记
  • 计算机技术认知实*报告
  • 六年级叙事作文:我的小乌龟_600字
  • 英语:Unit-3-《I-used-to-be-afraid-of-the-dark》课件(1)(鲁教版八年级下)(201908)
  • 欧莱雅眼霜简介
  • 戴尔电脑按什么u盘启动不了怎么办
  • poc, vul, exp都是什么意思呢?
  • 电梯安全管理培训课件_电梯的基本结构修订版
  • 人教版五年级语文上册第七单元测试卷答案
  • 中国石化销售有限公司河北沧州献县第九加油站企业信用报告-天眼查
  • 2、3、5倍数的特征实录与反思李慧
  • 长沙市雨花区桃阳矽砂矿企业信用报告-天眼查
  • 2019年中考历史考点过关:6.1-“上合青岛峰会”、文明的交流和对外交往课件
  • 郑大实践课考试答辩时间
  • 最新整理2019年入党积极分子党课培训思想汇报:幸福是什么.doc
  • 人教新目标九年级英语全册课件:unit9 Section A 3 Grammar Focus-4c (共33张PPT)
  • 最小生成树算法和单源最短路径算法
  • 电脑版