当前位置： 移动技术网 > IT编程>开发语言>Java > java实现单链表中是否有环的方法详解

java实现单链表中是否有环的方法详解

2019年07月22日  | 移动技术网IT编程  | 我要评论

这是一道微软经典笔试题，就是两个指针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;
    }


}

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网