I am trying to reverse a linked list using recursion. I had previously written code to do this using a simple while loop and it worked perfectly. I can't figure out why my recursion code isn't working.
#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();
}
Ouput:
110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
101 120
Expected output:
110 140 101 140 101 140 101 120
120 101 140 101 140 101 140 110
110 140 101 140 101 140 101 120