Связанный список имеет функцию просмотра цикла

Question

Я написал код для проверки, есть ли цикл ввода в связанном списке, но мой подход немного отличается от того, что используется в Интернете, он работает?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *p1,*p2;
    p1 = head;
    if(p1 == NULL) return 0;
    for(p1 = head;p1->next != NULL;p1 = p1->next){
        for(p2 = p1->next;p2 != NULL;p2=p2->next){
            if(p2 == p1) return 1;
            if (p2 == NULL) return 0;
        }
    }
    return 0;

}

Answer 1

Вы возвращаетесь слишком рано:

    for(p2 = p1->next;p2 != NULL;p2=p2->next){
        if(p2 == p1) return 1;
        if (p2 == NULL) return 0;
    }

Когда p2 становится НЕДЕЙСТВИТЕЛЬНЫМ, это просто означает, что нет цикла , включающего p1, не существует никакого цикла вообще.Возвращая 0 здесь, вы проверяете только головной узел на цикл.

Избавьтесь от дополнительного возврата, поэтому вы возвращаете 0 только тогда, когда искали все.

for(p1 = head;p1->next != NULL;p1 = p1->next){
    for(p2 = p1->next;p2 != NULL;p2=p2->next){
        if(p2 == p1) return 1;
    }
}
return 0;

РЕДАКТИРОВАТЬ:

Это все равно не будет работать, так как оно войдет в бесконечный цикл, если цикл не включает первый узел.Правильный способ справиться с этим - проверить каждый узел по всем найденным ранее узлам.Это можно сделать, поместив узлы в список по мере их посещения.Если узел уже существует в списке до того, как вы добавите его, вы нашли цикл.

В качестве альтернативы, вы можете поставить флаг «посещен» в каждом узле, инициализированном 0. Затем пройти по списку, установив флаг, как выидти.Если флаг уже установлен, у вас есть цикл.