如何使用递归反转链表

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的私有成员。

我没有查看过您的所有函数实现，但函数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使用辅助函数，则该函数应该是私有静态成员函数。列表的用户不得直接调用该列表。

这是一个示范节目。

#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

Answer 2

您的代码是多余的，您不需要那么多的局部变量和函数参数来实现递归。同样在此部分：

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

当next_node == nullptr时，您似乎将nullptr分配给了您的head。

修正版本：

void repeat(node* previous, node* current)
{
node* next_node = current->next;
current->next = previous;
if (next_node == nullptr)
{
head = current;
return;
}
repeat(current, next_node);
}
void recursive_reverse()
{
repeat(nullptr, head);
}

除此之外，您还有内存泄漏，因为您从未delete您分配的内存。实现析构函数并显式地将副本构造函数/赋值标记为deleted(如果有时间，也可以实现它们(：

LinkedLists(const LinkedLists& other) = delete;

以避免进一步的错误并遵守三(或五，或零(规则。