Это классический письменный тестовый вопрос Microsoft. Два указателя h1 и h2 перемещаются по односвязному списку с самого начала. h1 каждый раз перемещается на 1 шаг вперед, а h2 каждый раз перемещается вперед на 2 шага. Если h2 встречает NULL, это означает, что. кольцо не существует ; Если h2 касается h1, который должен находиться за ним, это означает, что петля существует (т. е. возникает петля).
Если кольцо не существует, h2 сначала должен встретить NULL:
Если кольцо существует, h2 и h1 обязательно встретятся, и точка встречи находится внутри кольца: h2 проходит быстрее, чем h1, и определенно не встретится в начале связанного списка без кольца, поэтому, когда h1 и h2 оба входят кольцо Наконец, каждое движение h2 будет уменьшать зазор между h2 и h1 в прямом направлении на 1. Наконец, зазор между h1 и h2 сократится до 0, то есть они встретятся.
public static void main(String args[]){
Список SingleList = новый SingleList();
for(int i=0;i<100;i++){
список.добавить(я);
}
System.out.print(SingleList.isExistingLoop(список));
}
}
общественный узел (значение объекта) {
this.data = значение;
}
общественный узел() {
this.data = ноль;
this.next = ноль;
}
}
частная недействительная инициализация () {
этот.размер = 0;
this.head = новый узел();
}
общественный сингллист () {
инициализация();
}
общедоступное логическое значение содержит (значение объекта) {
логический флаг = ложь;
Узел p = head.next;
в то время как (р! = ноль) {
если (value.equals (p.data)) {
флаг = правда;
перерыв;
}еще(
р = п.следующий;
)
}
флаг возврата;
}
public boolean add(значение объекта){
если(содержит(значение))
вернуть ложь;
еще{
Узел p = новый Узел (значение);
p.next = head.next;
head.next = р;
размер++;
}
вернуть истину;
}
}