如何反转我的链表。我写了以下代码，但这只给出了第一个节点的数据作为输出

Question

Node *reverse(Node *head)
{
Node *answer = NULL, *p = head, *address = NULL;
while (p != NULL)
{
address = p;
address->next = answer;
answer = address;
p = p->next;
}
return answer;
}

Answer 1

为了反转单链表，您需要在内存中保留一个节点才能反向重新链接。

它可能看起来像这样：

Node* reverse(Node* head) {
if(head) {                               // must have at least one node
Node* curr = head->next;             // head + 1
head->next = nullptr;                // this will be the new last node
Node* next;                          // for saving next while relinking
while(curr) {                        // while curr != nullptr
next = curr->next;               // save the next pointer
curr->next = head;               // relink backwards
head = curr;                     // move head forward
curr = next;                     // move curr forward
}
// head now points at the new start of the list automatically
}
return head;
}

演示

Answer 2

我写了下面的代码，但这只给出了第一个节点的数据作为输出

因为，在reverse()函数中，您正在从列表的其余部分断开第一个节点的链接并返回它。

看看这部分代码：

address = p;
address->next = answer;
answer = address;
p = p->next;

在while循环的第一次迭代中，这就是发生的情况：

指针address将指向列表的head(因为p是用head初始化的(，在下一条语句中，您正在执行address->next = answer(请注意，answer是用NULL初始化的(。因此，address->next被分配给NULL。指针p和指针address仍然指向同一节点。在此之后，您正在执行p = p->next，这将把NULL分配给p，因为p->next是NULL。由于p是NULL，while循环条件导致false，循环退出，函数最终返回第一个节点。

在将answer分配给address->next之前，您应该将p分配给它的next，如下所示：

while (p != NULL)
{
address = p;
p = p->next;   // moved up
address->next = answer;
answer = address;
}

建议：

在C++中，应该使用nullptr而不是NULL。

Answer 3

反转链表本质上相当于翻转箭头：

Original: A->B->C->D->null
Intermediate: null<-A<-B<-C<-D
Reversed: D->C->B->A->null

void reverseList(void)
{
Node *prev = nullptr;
Node *curr = head;
while (curr)
{
Node *nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
head = prev;
}

解决方案的关键是使用以前和当前的节点策略来循环列表。在第二行和第三行，我分别将prev设置为null和将curr设置为head。接下来，我设置while循环，它将一直运行到curr等于null或到达列表的末尾。在while循环正文的第3行和第4行中，我将prev设置为curr，将curr设置为nxt，以帮助我在列表中移动并保持遍历，同时跟踪先前和当前节点。

我将当前节点的下一个存储在临时节点nxt中，因为它稍后会被修改。

现在，curr->next = prev是做一些工作的语句。箭头的翻转通过该语句进行。我们不指向下一个节点，而是将当前节点的下一个指向上一个节点。

现在，我们只需要处理头部节点。在最后一行head=prev上，prev是列表中的最后一个节点。我们将head设置为列表中的prev节点，这就完成了反转列表的代码。

假设您在可视化算法时遇到任何问题。在这种情况下，为了更好地理解while循环中的每一行，您甚至有权打印存储在当前和以前节点中的数据。希望这能帮助我们了解如何反转链表。