Java implementation of a single linked list of whether there is a ring method

  • 2020-04-01 01:56:27
  • OfStack

This is a classic Microsoft pen question, is that the two Pointers h1, h2 from the beginning to traverse the single linked list, h1 each step forward, h2 each step forward 2 steps, if h2 encountered NULL, that ring does not exist; If h2 touches h1, which should be behind it, the ring exists (that is, the ring has occurred).

      If the ring does not exist, h2 must first encounter NULL:

      If ring exists, h1 and h2 will meet, and meet the point within the ring: h2 faster than the speed of h1 traversal, certainly not at the beginning of the loop list part of the meet, so when the h1, h2 is entering the ring, h2 every move can make between h1 and h2 on the direction of gap 1, finally, make the h1 and h2 gap reduced to 0, also is met


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; //The data object that the node stores
    public Node next; //A reference to the next node
    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;
    }

}


Related articles: