我的函数反转循环链表有什么问题

Question

我试图使用三个指针反转一个循环链表，但它正在运行。程序已执行，但我认为函数未执行。所以请检查一下，在我的反向函数中发现了错误。

void reverse()
{
struct node *p, *q, *r;
p=head;
p=q=NULL;
int flag = 0;
while(p->next != NULL)
{
flag = 1;
r=q;
q=p;
p=p->next;
q->next = r;
}
p->next = q;
head = q; 
}

Answer 1

您的代码中存在以下几个问题：

• 首先设置p = head，但在下一个语句中清除它。您可能打算用NULL初始化r，但错误地分配给了p。

• 最后的作业是错误的。您将错过一个值。当您看到p->next刚刚被分配了q的值时，head应该被分配给q是没有意义的，因为很明显p是的前身。您应该执行head = p而不是head = q。

• 当列表为空时，即当head为NULL时，该代码将失败。在这种情况下，while条件将引用一个NULL指针。您可以为head == NULL添加一个特定的if语句。

• 不重要，但flag似乎没有任何作用。你可以放下它。

void reverse()
{
struct node *p, *q, *r;
if (head == NULL) return;  // <--
p = head;
q = r = NULL;  // <--
while (p->next != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
p->next = q;
head = p;  // <-- 
} 

现在，只需允许while循环再进行一次迭代，就可以减少代码。然后，您不需要head == NULL的特殊条件，也不需要在循环之后对p->next进行额外的赋值(因为这将在额外的迭代中发生(：

void reverse()
{
struct node *p, *q, *r;
p = head;
q = r = NULL;
while (p != NULL)  // changed!
{
r = q;
q = p;
p = p->next;
q->next = r;
}
head = q;  // <-- now it should be q!
} 

Answer 2

在函数体的第三行中，执行

p=NULL

然后在while循环中，您访问

p->next

但是，由于这里p本身是一个NULL指针，这会给您带来一个错误。

如果您还有任何疑问，请随时发表评论。