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に減少させ、すなわち出会う.
リングが存在しない場合は、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;
}
};