C++递归实现链表反转失效，仅输出节点5问题求解

你的递归反转逻辑核心指针操作没有错，但存在两个致命问题导致运行结果不符合预期：

• reverse 函数定义为无返回值类型，递归执行到链表尾部（也就是反转后的新头节点）时，没有把新头节点的地址传回主函数，主函数里的head指针仍然指向反转前的旧头节点（也就是反转后的尾节点，它的next被置为NULL），打印时自然只能输出这一个节点的值。
• 递归终止条件的返回值没有承担传递新头节点的作用，仅做了空返回，丢失了新链表的起点地址。

把reverse函数修改为返回node*类型，递归触达尾节点时返回该节点作为新头，每一层递归完成局部指针反转后，持续将新头地址向上层返回，主函数调用时接收返回值更新原头指针即可。
完整可运行代码如下：

#include <iostream>
using namespace std;
class node{
    public:
    int data;
    node* next;
};

node* reverse(node* head)
{
   // 递归终止：空节点/当前是尾节点，直接返回当前节点作为新头
   if (!head || !(head -> next))
    {return head;}
    node* new_head = reverse(head->next);
    head->next->next=head;
    head->next=NULL;
    // 把新头持续向上返回
    return new_head;
}

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);
     // 接收反转后的新头节点
     head = reverse(head);
    print(head);
    return 0;
}

运行上述代码会输出预期结果1 0 2 3 4 5。

递归反转链表的核心思路可以拆成三步：

• 先递归把当前节点之后的子链表全部反转，拿到子链表反转后的新头
• 把当前节点挂到它原来的下一个节点的后面（也就是反转后子链表的尾部），再把当前节点的next置空，避免出现环
• 整个过程中反转后的新头节点始终是原链表的尾节点，需要通过返回值一层层传递到最外层调用处，不能丢失。

内容的提问来源于stack exchange，提问作者Rayman Sodhi