Member 13277493 Ответов: 2

Цикл в связанном списке идет до бесконечности


Я создал связанный список и хочу создать в нем цикл, который я могу обнаружить, но когда я пишу "temp->next->next=temp->next->next", он становится бесконечным. Я не понимаю, почему это так, я не вызываю эту функцию рекурсивно, что может привести к таким вещам.

#include <iostream>
#include <unordered_set>



class linkedList
{
private:
    struct node
    {
        int data;
        node *next;
    };
    node *head;

public:
    linkedList():head(nullptr)
    {

    }
    ~linkedList()
    {
        cleanUp(head);
    }
    void cleanUp(node *temp);
    void _push(node *&temp, int key);
    void push(int key)
    {
        _push(head, key);
    }

    void _print(node *temp);
    void print()
    {
        _print(head);
    }

    bool detectLoop(node *&temp);
    void loop()
    {
        std::cout<<detectLoop(head)<<std::endl;
    }
    void makeLoop(node *temp);
    void made()
    {
        makeLoop(head);
    }
};

void linkedList::_push(node *&temp, int key)
{
    node *newNode=new node;
    newNode->data=key;
    newNode->next=temp;
    temp=newNode;
}

void linkedList::cleanUp(node *temp)
{
    while(temp)
    {
        node *it=temp;
        temp=temp->next;
        delete it;
    }
}

bool linkedList::detectLoop(node *&temp)
{

    if(temp==nullptr || temp->next== nullptr)
    {
        return false;
    }

    node *first=temp;
    node *second=temp->next;

    while(second!= nullptr)
    {
        if(first==second)
        {
            return true;
        }

        first=first->next;
        second=second->next->next;
    }


}

void linkedList::makeLoop(node* temp)
{
    temp->next->next->next=temp->next->next;
}

void linkedList::_print(node *temp)
{
    while(temp)
    {
        std::cout<<temp->data<<" ";
        temp=temp->next;
    }
}



int main()
{
    linkedList l;
    l.push(7);
    l.push(8);
    l.push(1);
    l.push(7);

    l.made();

    l.loop();

    l.print();

}


Что я уже пробовал:

Я попытался понять это с помощью отладчика

2 Ответов

Рейтинг:
19

CPallini

Ваш код правильно обнаруживает цикл, а затем повторяется бесконечно, потому что print сам метод обращен к циклу.


Member 13277493

Спасибо!

CPallini

Добро пожаловать.

Рейтинг:
0

Kornfeld Eliyahu Peter

Это потому что temp->next->next теперь указывает на себя...
Пусть говорят, что a является temp->next->next...
а теперь садись a->next = a...


Member 13277493

Это означает, что я должен подключить конечный узел цикла к nullptr, не так ли?