欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

java實(shí)現(xiàn)單鏈表中是否有環(huán)的方法詳解

 更新時(shí)間：2013年05月04日 17:47:26   作者：  
本篇文章介紹了，用java實(shí)現(xiàn)單鏈表中是否有環(huán)的方法詳解。需要的朋友參考下

這是一道微軟經(jīng)典筆試題，就是兩個(gè)指針h1,h2都從頭開始遍歷單鏈表，h1每次向前走1步，h2每次向前走2步，如果h2碰到了NULL，說明環(huán)不存在；如果h2碰到本應(yīng)在身后的h1說明環(huán)存在（也就是發(fā)生了套圈）。

    如果環(huán)不存在，一定是h2先碰到NULL：

    如果環(huán)存在，h2與h1一定會(huì)相遇，而且相遇的點(diǎn)在環(huán)內(nèi)：h2比h1遍歷的速度快，一定不會(huì)在開始的那段非環(huán)的鏈表部分相遇，所以當(dāng)h1,h2都進(jìn)入環(huán)后，h2每次移動(dòng)都會(huì)使h2與h1之間在前進(jìn)方向上的差距縮小1，最后，會(huì)使得h1和h2差距減少為0，也即相遇

復(fù)制代碼 代碼如下:

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));
}
}


復(fù)制代碼 代碼如下:

package org.myorg;
public class Node{
    public Object data; //節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)對(duì)象
    public Node next; //指向下一個(gè)節(jié)點(diǎn)的引用

    public Node(Object value){
        this.data = value;
   }

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

}


復(fù)制代碼 代碼如下:

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;
    }


}

相關(guān)文章

最新評(píng)論