我已经用递归做了链表的逆操作，但是指针实际上是如何工作的有点混乱。如果我交换下面代码中的语句1和2，程序将不会运行。为什么？因为我假设(*head)->next = nullptr将设置*temp = nullptr，所以(*temp)->next = *head没有意义，但是如果这是真的，那么在下面的代码中，即使在语句1之后，(*head)->next也被设置为nullptr，所以它应该设置 *temp等于nullptr，并且据此它不应该反转链表，但是实际上代码反转了链表，怎么做？
void push(struct node*& tail, int v)
{
struct node* newNode = new node;
newNode->data = v;
newNode->next = tail;
tail = newNode;
}
void reverse_ll3(struct node* *rootAddress, struct node* *head, struct node* *temp)
{
if(!(*temp))
{
*rootAddress = *head;
return;
}
reverse_ll3(rootAddress, &((*head)->next), &((*temp)->next));
(*temp)->next = *head; // --------------1
(*head)->next = nullptr; // --------------2
}
int main()
{
struct node* head = NULL;
struct node* curr;
push(head, 60);
push(head, 50);
push(head, 40);
push(head, 30);
push(head, 20);
push(head, 10);
print_list(head);
cout << endl;
curr = head;
reverse_ll3(&head,&curr,&(curr->next));
print_list(head);
cout << endl;
return 0;
}
1条答案
按热度按时间6rqinv9w1#
编辑日期：
main函数中的链表初始为：
其中
e0,d0...q0是下一个节点地址设
x0,e0,d0,...q0存储在以下地址：e8, f4, e4, d4, c4, b4, a4即假设当前地址为 e10，则通过curr = head，e10 还包含 x0
我正在将
e8(&head), e10(&curr), f4(&(curr->next))传递给reverse_ll3当
temp = a4 then (!(*a4)) => (!(q0)) is true (q0 is nullptr)将执行if条件时，根地址包含 e8，头包含 b4*rootAddress = *head; i.e *e8 = *b4 => *b4 is a0现在递归将展开
第1次退绕
(*temp)->next = *head，此处临时包含 b4，标题包含 c4*b4 = a0, *c4 = b0(*b4)->next = *c4* is a0->next = b0a0->next是存储在 a4 中的 q0，因此 a4 内容 q0 将被 b0 替换，即 a0 现在包含 60|b0 且 a4 包含 b0(*head)->next = nullptr(*c4)->next = b0->next = nullptr，因此现在 a0 将替换为 nullptr，即 b0 现在包含 *50|空 * 且 b4 包含 a0第2次退绕
此处温度包含 c4，标题包含 d4
(*c4)->next = (*d4)(b0)->next = c0同样，a0 将替换为 c0，即现在 b0 包含 *50|并且 b4 包含 c0
注：由于 a4 包含 b0（以前 b0 包含 50|null，现在null替换为 c0）且 b0 包含 50|c0 这将从 a0（60）隐式创建链接|b0） 至 b0（50|（c）
(*d4)->next = c0->next = nullptr现在 b0 将替换为 nullptr，即 c0 现在包含 *40|空 * 且 c4 包含 b0类似地，对于其他节点，将执行相同的步骤，最后 e0 将为 nullptr
注：我们还可以做一项改进，我们甚至可以从reverse_ll3中删除
(*head)->next = nullptr，并在reverse_ll3函数调用后在main函数中添加curr->next = nullptr，因为在最后curr->next(e0)需要为 nullptr。