递归地反转链表

Question

我的递归技能相当生疏。我一直在思考这个问题，也在论坛上搜索了很长时间，但仍然无法理解。我试图实现反向链表使用递归。为什么我的反向函数不工作?

当我试图看到反向链表时，它只打印5作为结果，而结果应该是1 0 2 3 4 5。

#include <iostream>
using namespace std;
class node{
public:
int data;
node* next;
};
void reverse(node* head)
{
if (!head || !(head -> next))
{return ;}
reverse(head->next);
head->next->next=head;
head->next=NULL;


}
void print(node* n){
while(n!=NULL)
{
cout<<n->data<<" ";
n=n->next;
}
cout<<"n";
}
void insert(node** head,int x)
{
node* one=new node();
one->data=x;
one->next= *head;
*head=one;
}
int main()
{   node* head=NULL;
insert(&head,1);
insert(&head,0);
insert(&head,2);
insert(&head,3);
insert(&head,4);
insert(&head,5);
reverse(head);
print(head);
return 0;
}

Answer 1

您的函数通过值获取head指针，因此调用者将永远不会看到其head指针更改，但很明显，当列表反转时，head指针应指向以前是尾部节点的节点。

解决这个问题的一种方法是使用引用传递(使用&)，然后确保将head指针移动到原始列表中的最后一个节点。这可以通过在每次递归调用中执行head = head->next来实现，直到达到基本情况。

修正功能:

void reverse(node* &head)
{
if (head == nullptr || head -> next == nullpr) {
return;
}
node* tail = head; // current head will be the tail in the reversed list
head = head->next; // head should walk to the end of the list
// This will reverse the sublist, and make the head reference the last node
reverse(head);
// Make tail of the sublist (tail->next) point to the new tail
tail->next->next = tail; 
tail->next = nullptr;
}