c++ - 如何使用递归反转链表？

Question

我正在尝试使用递归来反转链表。我之前使用简单的 while 循环编写代码来执行此操作，并且效果很好。我不明白为什么我的递归代码不起作用。

#include<iostream>

using std::cout;
using std::endl;

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

class LinkedLists
{
    private: 
    node* head;
    node* temp;
    
    public:
    LinkedLists() // default constructor
    {
        head = NULL;
        temp = NULL;
    }

    void add_data(int d)
    {   
        node* new_node = new node; // create a pointer to the new node
        new_node->next = NULL;
        new_node->data = d;
        if (head == NULL)
        {   head = new_node;
            temp = head;
        }
        else
        {   
            temp = head;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            temp->next = new_node; // final node now points to the new_node
        }

    }

    void print_list()
    {
        temp = head;
        while(temp!=NULL)
        {
            std::cout<<temp->data<<" ";
            temp = temp->next;
        }
    }

    void reverse()
    {
        // reverse a linked list
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        while(next_node != NULL)
        {
            temp_ptr->next = prev_node;
            prev_node = temp_ptr;
            temp_ptr = next_node;
            next_node = temp_ptr->next;
        }

        temp_ptr->next = prev_node;

        head = temp_ptr;

    }

    void repeat(node* prev_node, node* temp_ptr,node* next_node)
    {
        temp_ptr->next = prev_node;
        prev_node = temp_ptr;
        temp_ptr = next_node;

        if (next_node != NULL)
        {
            next_node = temp_ptr->next;
            repeat(prev_node,temp_ptr,next_node);
        }
        head = temp_ptr;
    }

    void recursive_reverse()
    {
        node* prev_node;
        node* next_node;
        node* temp_ptr;

        prev_node = NULL;
        temp_ptr = head;
        next_node = temp_ptr->next;

        repeat(prev_node,temp_ptr,next_node);

    }
};

int main()
{
    LinkedLists l; // create a linked list object
    l.add_data(110);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(140);
    l.add_data(101);
    l.add_data(120);

    cout<<endl;
    l.print_list();


    l.reverse();

    cout<<endl;
    l.print_list();


    l.recursive_reverse();
    cout<<endl;
    l.print_list();

}

输出:

110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
101 120

预期输出:

110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
110 140 101 140 101 140 101 120

Answer 1

对于初学者来说，不清楚为什么链表的类有复数名称。

class LinkedLists
               ^^^  

像LinkedList这样的命名，不以's'结尾会更自然。

数据成员temp 是多余的，应该删除。相反，您可以将此数据成员替换为成员函数中的局部变量。

node 结构应该是 LinkedList 类的私有(private)成员。

我没有查看您所有的函数实现，但是函数 recursive_reverse 可以按以下方式定义，如下面的演示程序所示。

给你。

#include <iostream>
#include <functional>

class LinkedList
{
private: 
    struct node
    {
        int data;
        node* next;
    } *head = nullptr;


public:
    LinkedList() = default;

    // These two special member functions you can implement yourself
    LinkedList( const LinkedList &) = delete;
    LinkedList & operator =( const LinkedList & ) = delete;

    ~LinkedList()
    {
        clear();
    }
    
    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }
    }
    
    void add_data( int d )
    {   
        node **current = &head;
        
        while ( *current ) current = &( *current )->next;
        
        *current = new node { d, nullptr };
    }       

    friend std::ostream & operator <<( std::ostream &os, const LinkedList &list )
    {
        for ( const node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->data << " -> ";
        }
        
        return os << "null";
    }

    void recursive_reverse()
    {
        if ( head != nullptr && head->next != nullptr )
        {
            node *current = head;
            head = head->next;
            
            recursive_reverse();
            
            current->next->next = current;
            current->next = nullptr;
        }
    }
};

int main() 
{
    LinkedList list; // create a linked list object
    const int N = 10;
    
    for ( int i = 0; i < N; i++ )
    {
        list.add_data( i );
    }       

   
    std::cout << list << '\n';


    list.recursive_reverse();

    std::cout << list << '\n';

    list.recursive_reverse();

    std::cout << list << '\n';

    return 0;
}

程序输出为

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

如果要为成员函数 recursive_reverse 使用辅助函数，则该函数应该是私有(private)静态成员函数。列表用户不得直接调用。

这是一个演示程序。

#include <iostream>
#include <functional>

class LinkedList
{
private: 
    struct node
    {
        int data;
        node* next;
    } *head = nullptr;

    static void repeat( node *previous, node * &head )
    {
        if ( head )
        {
            node *current = head;
            
            if ( head->next ) 
            {
                head = head->next;
                repeat( current, head );
            }
            
            current->next = previous;
        }
    }
    
public:
    LinkedList() = default;
    ~LinkedList()
    {
        clear();
    }
    
    void clear()
    {
        while ( head )
        {
            delete std::exchange( head, head->next );
        }
    }
    
    void add_data( int d )
    {   
        node **current = &head;
        
        while ( *current ) current = &( *current )->next;
        
        *current = new node { d, nullptr };
    }       

    friend std::ostream & operator <<( std::ostream &os, const LinkedList &list )
    {
        for ( const node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->data << " -> ";
        }
        
        return os << "null";
    }
    
    void recursive_reverse()
    {
        repeat( nullptr, head );
    }
};

int main() 
{
    LinkedList list; // create a linked list object
    const int N = 10;
    
    for ( int i = 0; i < N; i++ )
    {
        list.add_data( i );
    }       

   
    std::cout << list << '\n';


    list.recursive_reverse();

    std::cout << list << '\n';

    list.recursive_reverse();

    std::cout << list << '\n';

    return 0;
}

程序输出与上图相同

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null