이것은 고전적인 Microsoft 작성 테스트 질문입니다. 두 포인터 h1과 h2는 처음부터 단일 연결 목록을 탐색합니다. h1은 매번 1단계 앞으로 이동하고 h2는 NULL을 만나면 다음을 의미합니다. ring이 존재하지 않습니다. ; h2가 그 뒤에 있어야 하는 h1에 닿으면 루프가 존재한다는 의미입니다(즉, 루프가 발생함).
링이 존재하지 않으면 h2는 먼저 NULL을 만나야 합니다.
링이 존재하는 경우 h2와 h1은 확실히 만날 것이며 만남의 지점은 링 내에 있습니다. h2는 h1보다 빠르게 이동하며 링이 아닌 연결 목록의 시작 부분에서는 확실히 만나지 않으므로 h1과 h2가 모두 들어갑니다. 링 마지막으로, h2의 각 움직임은 h2와 h1 사이의 간격을 전방 방향으로 1만큼 감소시킵니다. 마지막으로, h1과 h2 사이의 간격은 0으로 감소합니다. 즉, 만나는 것입니다.
공개 정적 무효 메인(문자열 인수[]){
SingleList 목록 = 새로운 SingleList();
for(int i=0;i<100;i++){
목록.추가(i);
}
System.out.print(SingleList.isExistingLoop(목록));
}
}
공개 노드(객체 값){
this.data = 값;
}
공개노드(){
this.data = null;
this.next = null;
}
}
개인 무효 초기화(){
this.size = 0;
this.head = 새로운 Node();
}
공개 싱글리스트(){
초기화();
}
공개 부울 포함(객체 값){
부울 플래그 = false;
노드 p = head.next;
동안(p!=null){
if(value.equals(p.data)){
플래그 = 참;
부서지다;
}또 다른(
p = p.다음;
)
}
반환 플래그;
}
public boolean add(객체 값){
if(포함(값))
거짓을 반환;
또 다른{
노드 p = 새 노드(값);
p.next=head.next;
head.next = p;
크기++;
}
사실을 반환;
}
}