【java基础 13】两种方法判断hashmap中是否形成环形链表

java

导读:额,我介绍的这两种方法,有点蠢啊,小打小闹的那种,后来我查了查资料,别人都起了好高大上的名字,不过,本篇博客,我还是用何下下的风格来写。两种方法,一种是丢手绢法,另外一种,是迷路法。


这两种方法的基本思想:假设有环(顿时想到了三个数中找最大的,假设一个最大值有木有,更有木有想到一个排序算法呢?)


其实,这种方法时有个很高大上的名称的,叫做指针追赶法。不过,我刚开始想了半天没想明白,后来等我想明白了之后,哇塞,其实思想就是我小时候玩得丢手绢的游戏。

趣说指针追赶法:想象一下小时候玩丢手绢,自己是怎么死的?你妹的,就一个圈,往一个方向跑,自己跑的比别人慢,还没跑几步,然后就被追上了。反例:要是这不是一个圈,咱俩从一个地方往一个方向跑,你老人家跑的比我快,能追上不?(PS:想不明白的,就往死了想玩丢手绢是怎么死的。短跑健将抓小偷,是怎么跑到小偷前面被小偷嘲笑的)

好了,思想说完了,看看代码:

public class stringTest {

/**

* 内部类,模拟链表

* @author AngelHHX

*

*/

public static class Node{

int value;

Node next;

public Node(int n){

this.value=n;

this.next=null;

}

}

public static boolean hasLoop(Node n){

//定义两个指针,一个每次走一步,一个每次走两步

Node Point1=n;

Node Point2=n.next;

while(Point2!=null){

Point1=Point1.next;//每次走一步

Point2=Point2.next.next;//每次走两步

if(Point2==null) return false;//不存在环

int value1=Point1.value;

int value2=Point2.value;

if(value1==value2) return true;//存在环

}

return false;//当Point2为null,证明这个链表中只有一个元素

}

public static void main(String[] agrs) {

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

n1.next = n2;

n2.next = n3;

n3.next = n1;//构造一个带环的链表,去除此句表示不带环

System.out.println(hasLoop(n1));

}

}


二、迷路法(查表法)

这个方法的基本思想,真的跟我这个人有关,想明白这个方法的内涵,只需要我自己出门走一圈就OK了! 题外话啊,有小时候看过《少年包青天》的不?里面有一集,就是展昭中毒的那一集,然后公孙策和香香走进了一个树林里,她俩迷路了,然后香香扯那个裙子绑树上打标记,结果走着走着就又回到了原地!

额,想想自己迷路的时候,如果你发现你走了好久,结果又回到了某一个地方,内心崩溃:我他妈的走了半天,竟然还在原地打圈圈!(反正我是这样的)然后再想想数据结构中图的简单回路那一节内容,好好体会吧。

简单说来,就是将指针每走的一个节点记录下来,然后每次走一个节点,就去记录里面查,如果发现重复了,那么恭喜你,迷路了。(链表有环)

代码如下:

import java.util.HashMap;

public class stringTest {

/**

* 内部类,模拟链表

* @author AngelHHX

*

*/

public static class Node{

int value;

Node next;

public Node(int n){

this.value=n;

this.next=null;

}

}

public static boolean hasLoop(Node n){

Node Point1=n;

HashMap<Node,Node> HM=new HashMap<Node,Node>();

while(n!=null){

if(HM.get(Point1)!=null) return true;

else HM.put(Point1, Point1);

Point1=Point1.next;

if(Point1==null) return false;

}

return false;

}

public static void main(String[] agrs) {

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

n1.next = n2;

n2.next = n3;

n3.next = n1;//构造一个带环的链表,去除此句表示不带环

System.out.println(hasLoop(n1));

}

}



三、总结

以上就是关于是否有环的判断,突然有一种感觉,生活远远比写代码复杂的多!写代码真的跟生活经历有关,好好去体验生活,去经历,真的会很好!接下来的工作,就是把我草稿箱的那些要写的博客都写完,然后看看书!

对于java基础的东西,尤其是数据结构和算法方面的,自己真心比较弱,还请大家多多指教!PS:我这么一直看书,一直总结,在做项目的时候,再思考思考,有没有感觉到,我这是下次考数据结构,必过的节奏啊。。。。。。。。。。

以上是 【java基础 13】两种方法判断hashmap中是否形成环形链表 的全部内容, 来源链接: utcz.com/389932.html

回到顶部