JAvaは、単一チェーンテーブルにループがあるかどうかを判断する

3025 ワード

2つのポインタh 1、h 2はすべて最初から単鎖表を遍歴して、h 1は毎回1歩前進して、h 2は毎回2歩前進して、h 2がNULLにぶつかったら、リングが存在しないことを説明します;h 2が後ろにあるはずのh 1にぶつかると、リングが存在する(すなわち、スリーブが発生した)ことを示す.
リングが存在しない場合は、h 2がNULLに先に遭遇するに違いありません.
リングが存在する場合、h 2とh 1は必ず出会うし、出会った点はリング内:h 2がh 1より遍歴する速度が速く、必ず最初の非リングのチェーンテーブル部分で出会うことはないので、h 1,h 2がリングに入った後、h 2が移動するたびにh 2とh 1の間の前進方向の差を1縮小し、最後に、h 1とh 2の差を0に減少させ、すなわち出会う.

public class LinkedListNode {

	private static boolean isLoop(NodeList p)
	{
		NodeEntity slow = p.head ;
		NodeEntity fast = p.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) {
		NodeList list = new NodeList();
		
		for(int i=0;i<3;i++)
		{
			list.add(i);
		}
		
		System.out.println(isLoop(list));
		System.out.println(list.head.next.data);
		System.out.println(list.size);
		list.remove(1);
		System.out.println(list.head.next.data);
		System.out.println(list.head.next.next.data);
		System.out.println(list.size);
	}
};

class NodeEntity
{
   public Object data;      //    
   public NodeEntity next ; //      
   
   public NodeEntity(Object value){  
       this.data = value;  
   }  
   public NodeEntity()
   {
	   this.data = null ;
	   this.next = null ;
   }
};

class NodeList
{
	public int size ;
	public NodeEntity head ;
	
	public NodeList()
	{
		this.size = 0;
		this.head = new NodeEntity();   ;
	}
	
	public boolean contain(Object data)
	{
		boolean flag = false ;
		NodeEntity next = head.next ;
		while(next!=null)
		{
			if(next.data==data)
			{
				flag = true ;
				break ;
			}
			next = next.next ;
		}
		return flag ;
	}
	
	public boolean add(Object data)
	{
		if(contain(data))
		{
			return false ;
		}
		else
		{
			NodeEntity p = new NodeEntity(data);
			p.next = head.next ;
			head.next = p ;
			this.size++;
			return true ;
		}
	}
	public boolean remove(Object data)
	{
		NodeEntity current = head;  
		NodeEntity previous = head; //         
		boolean flag = true ;
         while (current.data != data) {  
             if (current.next == null) {  
            	 flag = false;  
            }  
            previous = current;
            current = current.next;
        }
        if(current == head) {
        	 head = head.next;  
        } else {
            previous.next = current.next;  
        }  
        return flag;
	}
};