链表插入在 for/while 循环中不起作用

Question

我正在学习DSA，并试图实现链表，但我编写的插入函数没有在for或while循环中工作，当我在循环外调用该函数时，情况就不一样了，它是这样工作的。我想不通，请有人帮我。

#include <iostream>
class Node {
public:
int data;
Node *next;
Node(int &num) {
this->data = num;
next = NULL;
}
};
class LinkedList {
Node *head = NULL;
public:
void insert(int num) {
Node *tmp;
if (head == NULL) {
head = new Node(num);
tmp = head;
} else {
tmp->next = new Node(num);
tmp = tmp->next;
}
}
void printList() {
Node *tmp = head;
while (tmp) {
std::cout << tmp->data << "  ";
tmp = tmp->next;
}
std::cout << std::endl;
}
void reverseList() {
Node *curr = head, *prev = NULL, *nextNode;
while (curr) {
nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
}
head = prev;
}
};
int main() {
LinkedList list1;
// This is not working
int num;
while (num != -1) {
std::cin >> num;
list1.insert(num);
}
// This is working
// list1.insert(1);
// list1.insert(2);
// list1.insert(3);
// list1.insert(4);
// list1.insert(5);
list1.printList();
list1.reverseList();
list1.printList();
return 0;
}

我预计插入后会出现这种情况

编辑：尽管@Roberto Montalti为我解决了这个问题，但在此之前，我尝试使用for循环传递递增值，这很有效，但当我拉出cin时，它就崩溃了。有人能告诉我引擎盖下面发生了什么事吗？

for (int i = 1; i <= 10; i++)
{
list1.insert(i);
}

Answer 1

当插入第n个项(排除第一个项(时，tmp是一个空指针，我不明白你在那里做什么，你正在分配给某个内存的next，然后你让该指针指向另一个位置，丢失之前分配的下一个指针，如果你想要最佳插入，你必须跟踪最后一个项。通过这种方式，您只分配给一些*tmp，然后超出范围将丢失所有数据。。。最好的方法是只保留一个指向最后插入项的指针，而不需要使用*tmp。

class LinkedList
{
Node *head = NULL;
Node *tail = NULL;
public:
void insert(int num)
{
if (head == NULL)
{
head = new Node(num);
tail = head;
}
else
{
tail->next = new Node(num);
tail = tail->next;
}
}
...
}

Answer 2

您需要循环直到到达列表的末尾，然后添加新节点。就像这样。

void insert(int num) {
Node *tmp = head;
if (head == NULL) {
head = new Node(num);
}
else {
while (tmp->next != NULL) {
tmp = tmp->next;
}
tmp->next = new Node(num);
}
}

Answer 3

首先，您需要为列表的尾部和头部定义一个节点，如下所示

Node *h;
Node *t;

您也可以将Node从LinkedList类中分离出来，这样您就可以很容易地修改

class Node{
public:
int data;
Node *next;
Node(int data, Node* next);
~Node();
};
Node::Node(int data, Node* next)
{
this->data= data;
this->next= next;
}
Node::~Node(){}
}

之后，您可以尝试将这些函数添加到LinkedList类中因此它可以处理其他特殊情况，如空列表或满列表等

void addToHead(int data){
Node *x = new Node(data,h);
h=x;
if(t==NULL){
t=x;
}

void addToTail(int data){
Node *x = new Node(data,NULL);
if(isEmpty()){
h=t=x;
}
else
{
t->next=x;
t=x;
}
}

现在，对于插入函数，请在实现Node类和其他函数之后尝试此操作

void insert(int v){
if(h==nullptr){addToHead(v); return;}
if(h->data>=v) {addToHead(v);return;}
if(t->data<=v) {addToTail(v); return;}
// In this case there is at least two nodes
Node *k=h->next;
Node *p=h;
while(k != nullptr){
if(k->data >v){
Node *z =new Node(v,k);
p->next=z;
return;
}
p=k;
k=k->next;
}
}

这样做的目的是在指针经过链表中的元素时不会丢失指针，这样就不会出现运行时错误。

我希望这对你有用。

Answer 4

插入函数出现问题。在此处阅读有关分段故障的信息https://www.geeksforgeeks.org/core-dump-segmentation-fault-c-cpp/#:~：text=Core%20Dump%2FSegmentation%20fault%20is，is%20known%20as%20core%20Dump。

为了快速解决问题，你可以使用这个

using namespace std;
#include <iostream>
class Node
{
public:
int data;
Node *next;
Node(int num)
{
this->data = num;
next = NULL;
}
};

class LinkedList
{
Node *head = NULL;

public:
void insert(int num)
{
Node *tmp= new Node(num);
tmp->next=head;
head=tmp;
}
void printList()
{
Node *tmp = head;
while (tmp)
{
std::cout << tmp->data << "  ";
tmp = tmp->next;
}
std::cout << std::endl;
}
void reverseList()
{
Node *curr = head, *prev = NULL, *nextNode;
while (curr)
{
nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
}
head = prev;
}
};

int main()
{
LinkedList list1;
// This is not working
int num,i=0,n;
cout<<"Type the value of n";
cin>>n;
while (i<n)
{
cin >> num;
cout<<num<<" "<<&num<<endl;
list1.insert(num);
i++;
}

list1.printList();
list1.reverseList();
list1.printList();

return 0;
}