c++ - 尝试使用递归和指向指针的指针来反转链表，但 reversell 函数未给出预期的正确输出

Question

我试图使用递归和指向指针的指针来反转链表，但 reversell 函数没有按预期正常工作。只有 reversell 函数有一些问题，所有其他函数都运行良好。我也在 insertlast 函数中使用了指向指针的指针，它工作正常。

其实我在关注 https://www.youtube.com/watch?v=KYH83T4q6Vs&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P&index=11这个视频，但我尝试使用指针指向指针。视频中显示的代码没有使用指针到指针。他使用 head 作为全局变量。

#include <iostream>
using namespace std;

struct node{
    int data;
    struct node* next;
};

void print(node* head){
    while(head !=  NULL){
        cout<<head->data<<" ";
        head=head->next;
    }
}

void reversell(node** head){
    node* temp = (*head);
    if(temp->next == NULL){
        (*head)=temp;
        return;
    }
    reversell(&(temp->next));
    node* temp1 = temp->next;
    temp1->next = temp;
    temp->next = NULL;

}

void insertlast(node** head,int x){
    node* temp = new node;
    temp->data=x;
    if((*head)==NULL){
        (*head)=temp;
        temp->next=NULL;
        return;
    }
    node* temp1=(*head);
    while((temp1->next) != NULL){
        temp1=temp1->next;
    }
    temp1->next=temp;
    temp->next=NULL;
}

int main()
{
    cout<<"How many numbers do you want to add to linked list"<<endl;
    int x;
    cin>>x;
    node* head=NULL;
    cout<<"Please Enter your numbers now"<<endl;
    for (int i=0;i<x;i++){
        int num;
        cin>>num;
        insertlast(&head,num);
    }
    print(head);
    cout<<endl;
    reversell(&head);
    print(head);
    return 0;
}

我目前得到如下所示的输出:

你要向链表中加入多少个数

5

请立即输入您的号码

1 2 3 4 5

1 2 3 4 5

1

进程结束，退出代码为 0

预期输出是:

你要向链表中加入多少个数

5

请立即输入您的号码

1 2 3 4 5

1 2 3 4 5

5 4 3 2 1

进程结束，退出代码为 0

Answer 1

试试这个

node *reverse (node *head) {
    // 2) reach the last element and return it
    if(head->next == NULL) {
        return head;
    } else {
        // 1) run revers for tail of our list
        node *new_head = reverse(head->next);
        // 3) relocate pointers
        // new_head = 5;
        // head = 4, head->next = 5, head->next->next = null
        head->next->next = head; // after this line head = 4, head->next = 5, head->next->next = 4
        head->next = NULL; // after this line head = 4, head->next = null, head->next->next = 4
        return new_head; // new_head = 5, new_head->next = 4 similarly recursion takes place further
    }
}

然后:

head = reverse (head);
print(head);