Перевернуть связанный список с помощью рекурсии

Question

Методы void reve(struct Node *head) и display(struct Node *head) принимают один аргумент - заголовок связанного списка. Я хочу напечатать весь связанный список, но моя функция отображения выводит только 4.

#include <iostream>

using namespace std;

struct Node {
    int data;
    struct Node *link;
};

void display(struct Node *head) {
    if (head == NULL) {
        return;
    }
    cout << head->data << "\t";
    display(head->link);
    //head = head->link;
}

struct Node *reve(struct Node *head) {
    struct Node *p = head;
    if (p->link == NULL) {
        head = p;
        return head;
    }
    reve(p->link);
    struct Node *temp = p->link;
    temp->link = p;
    p->link = NULL;
}

struct Node *insert(struct Node *head, int new_data) { 
    Node *new_node = new Node(); 
    new_node->data = new_data; 
    new_node->link = head; 
    head = new_node; 
    return head;
}

int main() {
    Node *head = NULL;
    head = insert(head, 1);
    head = insert(head, 2);
    head = insert(head, 3);
    head = insert(head, 4);
    cout << "The linked list is: ";
    //display(head);
    head = reve(head);
    display(head);
    return 0;
}

Вывод

Answer 1

display в порядке.

Первое, что я заметил, это то, что вы пытаетесь изменить скопированное значение. Например, строка 16. Этот код не имеет никакого эффекта.

Обратите внимание, что у вас есть ошибка при вставке: вы возвращаете head вместо new_node.

Ваша версия не работает для списков с более чем 1 элементом. reve() должен возвращать последний узел исходного списка, чего у вас нет, следовательно, lastNode не будет указывать на последний узел обращенного списка. Поэтому я советую вам оставить это в стороне.

Итак, reve:

struct Node* reve(struct Node* head) {
    if (head->link == NULL) {
        return head;
    }

    struct Node* lastNode = reve(head->link);
    lastNode->link = head;
    head->link = NULL;

    return head;
}

и main:

int main() {
    Node* head = NULL;
    Node* last_node = head = insert(head, 1);
    head = insert(head, 2);
    head = insert(head, 3);
    head = insert(head, 4);
    head = reve(head);
    cout << "The linked list is: ";
    // Now, last_node is the new head
    display(last_node);
    return 0;
}

Answer 2

Если вы хотите рекурсивный способ:

Node* reverse(Node* head) 

{ 

    if (head == NULL || head->next == NULL) 

        return head; 



    /* reverse the rest list and put  

      the first element at the end */

    Node* rest = reverse(head->next); 

    head->next->next = head;

    head->next = NULL; 

    /* fix the head pointer */

    return rest; 

} 



/* Function to print linked list */

void print() 

{ 

    struct Node* temp = head; 

    while (temp != NULL) { 

        cout << temp->data << " "; 

        temp = temp->next; 

    } 

} 

Answer 3

В C ++ вам не нужно использовать ключевые слова struct или class, когда в качестве спецификатора типа используется уже объявленная структура или класс.

Функция reve имеет неопределенное поведение.

Прежде всего head может быть равно nullptr. В этом случае это выражение

if (p->link == NULL) {

вызывает неопределенное поведение.

Во-вторых, функция ничего не возвращает в случае, когда p->link не равно nullptr.

    //...
    reve(p->link);
    struct Node *temp = p->link;
    temp->link = p;
    p->link = NULL;
}

Вот демонстрационная программа, которая показывает, как функции могут быть реализованы. Я использовал ваш C подход, включив ключевое слово struct, когда структура используется в качестве спецификатора типа.

#include <iostream>

struct Node
{
    int data;
    struct Node *link;
};

struct Node * insert( struct Node *head, int data )
{
    return head = new Node{ data, head };
}

struct Node * reverse( struct Node *head )
{
    if ( head && head->link )
    {
        struct Node *tail = head;

        head = reverse( head->link );

        tail->link->link = tail;
        tail->link = nullptr;
    }

    return head;
}

std::ostream & display( struct Node *head, std::ostream &os = std::cout )
{
    if ( head )
    {
        os << head->data;
        if ( head->link )
        { 
            os << '\t';
            display( head->link, os );
        }
    }

    return os;
}

int main() 
{
    struct Node *head = nullptr;

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        head = insert( head, i );
    }   

    display( head ) << '\n';

    head = reverse( head );

    display( head ) << '\n';

    return 0;
}

Вывод программы:

9   8   7   6   5   4   3   2   1   0
0   1   2   3   4   5   6   7   8   9

Answer 4

Функция reve не возвращает значение, если p->link не NULL.

Поскольку head имеет более 1 элемента, head = reve(head); имеет неопределенное поведение.

Обращение связанного списка гораздо проще реализовать в простом l oop, чем с помощью рекурсии:

struct Node *reve(struct Node *p) {
    if (p != NULL) {
        struct Node *prev = NULL;
        while (p->link) {
            struct Node *next = p->link;
            p->link = prev;
            prev = p;
            p = next;
        }
    }
    return p;
}

Если ваша задача требует рекурсии, вы можете сделать извлечение первого узла, перевернув оставшуюся часть список и добавить первый узел. Помните, что это не хвостовая рекурсия, поэтому любой достаточно длинный список может вызвать переполнение стека .

struct Node *reve(struct Node *head) {
    if (head != NULL && head->link != NULL) {
        struct Node *first = head;
        struct Node *second = head->link;
        head = reve(second);
        first->link = NULL;   // unlink the first node
        second->link = first; // append the first node
    }
    return head;
}