How to reverse a linked list using recursion?

Viewed 153

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
2 Answers

Your code is superfluous, you don't need that many local variables and function arguments to implement recursion. Also in this part:

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

you seem to assign nullptr to your head when next_node == nullptr.

Corrected version:

    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);
    }

Apart from that you have a memory leaks, because you never delete the memory that you allocated. Implement the destructor and mark your copy constructors/assignments as deleted explicitly (or you can also implement them, if you have time):

LinkedLists(const LinkedLists& other) = delete;

to avoid further bugs and to comply with the rule of three (or five, or zero).

For starters it is unclear why the class of the linked list has a plural name.

class LinkedLists
               ^^^  

It will be more natural to name it like LinkedList without ending 's'.

The data member temp is redundant and should be removed. Instead you can substitute this data member for local variables in member functions.

The structure node should be a private member of the class LinkedList.

I have not looked through all your function implementations but the function recursive_reverse can be defined the following way as it is shown in the demonstrative program below.

Here you are.

#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;
}

The program output is

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

If to use an auxiliary function for the member function recursive_reverse then the function should be a private static member function. The user of the list shall not call it directly.

Here is a demonstrative program.

#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;
}

The program output is the same as shown above

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
Related