Попытка перевернуть связанный список, используя рекурсию и указатель на указатель, но функция reversell не дает ожидаемого правильного вывода

Question

Я пытался перевернуть связанный список, используя рекурсию и указатель на указатель, но функция 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

Ваша функция reversell частично в порядке, но вы не сохранили вывод. Вы можете попробовать это:

void reverse(node* head, node **headRef)
{
    node* firstTemp = NULL;
    node* secondTemp = NULL;

    //empty list
    if(!head)
        return;

    firstTemp = head;
    secondTemp = firstTemp->next;

    //list has only one node
    if(!secondTemp)
    {
         *headRef = firstTemp;
         return;
    }

    reverse(secondTemp, headRef);

    secondTemp->next = firstTemp;
    firstTemp->next = NULL;
}

void reversell(node **head)
{
     reverse(*head, head);
}

Answer 2

попробуйте

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);