我正在尝试使用递归来反转链表。我之前使用简单的 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
最佳答案
对于初学者来说，不清楚为什么链表的类有复数名称。
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
关于c++ - 如何使用递归反转链表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/63409754/