链表中的循环变为无穷大 [英] Loop in a linked list goes to infinity

问题描述

我创建了一个链表，我想在其中创建一个我可以检测到的循环，但是当我写temp-> next-> next-> next = temp-> next->接下来它变得无限。我不明白为什么会这样，我不会递归地调用那个函数来导致那种事情。

 #include< iostream> 
 #include< unordered_set> 
 
 
 
 class linkedList 
 {
 private：
 struct node 
 {
 int data; 
 node * next; 
}; 
节点* 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; 
删除它; 
} 
} 
 
 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 - >下一步 - >接着= TEMP->下一步 - >接着， 
} 
 
 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（）; 
 
} 
 

我的尝试：



我试图用调试器来理解它

解决方案

你的代码正确地检测到循环然后无休止地迭代，因为 print 方法本身面向循环。

因为 temp-> next-> next 现在指向自己...

假设 a 是 temp-> next- >下一个 ...

现在你设置 a-> next = a ...

I have created a linked list and I want to create a loop in it which I can detect, but when I write "temp->next->next->next=temp->next->next" it goes infinite. I don't understand why is it like that, I don't call that function recursively that can result in that kind of things.

#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();

}

What I have tried:

I have tried to understand it with debugger

解决方案

Your code correctly detects the loop then iterate endlessly because the print method itself faces the loop.

That because temp->next->next now points to itself...
Let say that a is temp->next->next...
now you set a->next = a...

这篇关于链表中的循环变为无穷大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！