java实现单链表中是否有环的方法详解
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
这是一道微软经典笔试题，就是两个指针h1,h2都从头开始遍历单链表，h1每次向前走1步，h2每次向前走2步，如果h2碰到了NULL，说明环不存在；如果h2碰到本应在身后的h1说明环存在（也就是发生了套圈）。
如果环不存在，一定是h2先碰到NULL：
如果环存在，h2与h1一定会相遇，而且相遇的点在环内：h2比h1遍历的速度快，一定不会在开始的那段非环的链表部分相遇，所以当h1,h2都进入环后，h2每次移动都会使h2与h1之间在前进方向上的差距缩小1，最后，会使得h1和h2差距减少为0，也即相遇
package org.myorg;
public class Test{
public static boolean isExsitLoop(SingleList a) {
Node<T> slow = a.head;
Node<T> fast = a.head; while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
return true;
}
return false;
}
public static void main(String args[]){
SingleList list = new SingleList();
for(int i=0;i<100;i++){
list.add(i);
}
System.out.print(SingleList.isExistingLoop(list));
}
}
package org.myorg;
public class Node{
public Object data; //节点存储的数据对象
public Node next; //指向下一个节点的引用
public Node(Object value){
this.data = value;
}
public Node(){
this.data = null;
this.next = null;
}
}
package org.myorg;
public class SingleList{
private int size;
private Node head;
private void init(){
this.size = 0;
this.head = new Node();
}
public SingleList(){
init();
}
public boolean contains(Object value){
boolean flag = false;
Node p = head.next;
while(p!=null){
if(value.equals(p.data)){
flag = true;
break;
}else(
p = p.next;
)
}
return flag;
}
public boolean add(Object value){
if(contains(value))
return false;
else{
Node p = new Node(value);
p.next=head.next;
head.next = p;
size++;
}
return true;
}
}
相关文章
多线程Thread,Runnable,Callable实现方式
这篇文章主要为大家详细介绍了Java多线程如何实现Thread,Runnable,Callable的方式，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2021-08-08
正则表达式异常强大,一直理解不深,用的也不深,这次项目中尝试,体会到了它的强大之处,这篇文章主要给大家介绍了关于Java正则表达式之全量匹配和部分匹配的相关资料,需要的朋友可以参考下2023-06-06
这篇文章主要介绍了JAVA Lock锁原理的相关资料，文中讲解非常细致，代码帮助大家更好的理解和学习，感兴趣的朋友可以了解下2020-07-07
这篇文章主要介绍了使用Java实现先查询缓存再查询数据库,文章围绕主题展开详细的内容介绍，具有一定的参考价值，需要的小伙伴可以参考一下2022-07-07
java序列化与ObjectOutputStream和ObjectInputStream的实例详解
这篇文章主要介绍了java序列化与ObjectOutputStream和ObjectInputStream的实例详解的相关资料,希望通过本文能帮助到大家，需要的朋友可以参考下2017-09-09
本篇文章介绍了，基于java内部类作用的深入分析。需要的朋友参考下2013-05-05
Java Hibernate中使用HQL语句进行数据库查询的要点解析
HQL是Hibernate框架中提供的关系型数据库操作脚本,当然我们也可以使用原生的SQL语句,这里我们来看一下在Java Hibernate中使用HQL语句进行数据库查询的要点解析:2016-06-06
Java中==与equals()及hashcode()三者之间的关系详解
最近也是在读Hollis的《深入理解Java核心技术》里面一节讲到了equals()和hashcode()的关系，对于这个高频面试点，咱们需要认真理清一下几者之间的关系2022-10-10
定义这个规范的目的是让项目中所有的文档都看起来像一个人写的，增加可读性，减少项目组中因为换人而带来的损失。下面给大家分享java开发命名规范，一起看看吧2017-03-03
这篇文章主要介绍了关于弗洛伊德算法求最短路径详解,弗洛伊德算法VS迪杰斯特拉算法:迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他项点的最短路径:弗洛伊德算法中每-个顶点都是出发访问点,需要的朋友可以参考下2023-07-07
最新评论