C++链表反向函数触发无限循环

Question

>我已经从一个数组创建了一个链表。它工作正常。但是当我尝试使用reverseList()函数反转列表时，它会启动一个无限循环。当我尝试显示列表时，它会重复显示最后两个成员。

#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *next;
};
node *reverseList(node *h)
{
node *p, *q, *r;
p = h->next;
q = h;
r = NULL;
while (p)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
h = q;
return h;
}
int main()
{
struct node *n, *h, *t;
int arr[] = {2, 5, 9, 6, 8};
n = new node;
t = n;
h = n;
n->data = arr[0];
for (int i = 1; i < 5; i++)
{
n = new node;
n->data = arr[i];
t->next = n;
t = n;
}
n->next = NULL;
node *p = reverseList(h);
while (p)
{
cout << p->data << " ";
p = p->next;
}
return 0;
}

Answer 1

在函数reverseList

node *reverseList(node *h)
{
node *p, *q, *r;
p = h->next;
q = h;
r = NULL;
while (p)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
h = q;
return h;
}

指针指向的第一个节点的初始q->nexth未设置为nullptr。它一直指向原始列表中的第二个节点。

那是在这句话之后

q = h;

在 while 循环之前，指针q->next未设置为nullptr。

此外，如果传递的参数是空指针，则该函数可以调用未定义的行为。

函数可以通过以下方式定义

node * reverseList( node *h )
{
node *q = nullptr;
for ( node *p = h; h != nullptr; p = h )
{
h = h->next;
p->next = q;
q = p;
}
h = q;
return h;
}

或者最好使用更有意义的名称，例如

node * reverseList( node *head )
{
node *new_head = nullptr;
for ( node *current = head; head != nullptr; current = head )
{
head = head->next;
current->next = new_head;
new_head = current;
}
return new_head;
}

请注意，当不再需要时，您需要为列表释放所有已分配的内存。