How to reverse a linked list using recursion?

Question

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

Unrelated: You use new but not delete. Your program leaks. Fixing that is more important than reversing it I'd say. — Ted Lyngmo
– Ted Lyngmo, Commented Aug 14, 2020 at 9:13
Where should I use delete? Wouldn't that delete the node? Or should I not use new in the first place? — Sabito
– Sabito, Commented Aug 14, 2020 at 9:30
If you create a LinkedLists and fill it with data and the LinkedLists goes out of scope - it's supposed to clear all the memory it's allocated. You just leave it allocated. If you do this in a loop you'll run out of memory eventually. You can sometimes use smart pointers but for this type of thing, raw pointers is probably what you want - but it makes memory management really important. A first step could be a destructor, like: ~LinkedList() { for(node* temp; head; head = temp) { temp = head->next; delete head; } } or similar. — Ted Lyngmo
– Ted Lyngmo, Commented Aug 14, 2020 at 9:35
About the delete question: just implement the destructor LinkedLists::~LinkedLists() which will delete all previously allocated data. You can also do it recursively, however usually it is better to do this kind of things iteratively for large objects. — pptaszni
– pptaszni, Commented Aug 14, 2020 at 9:38
@Yatin Yes, you need a destructor (like the one I showed above) but you also need to think about The rule of three/five/zero — Ted Lyngmo
– Ted Lyngmo, Commented Aug 14, 2020 at 9:39

Vlad from Moscow · Accepted Answer · 2020-08-14 11:59:07Z

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

pptaszni · Accepted Answer · 2020-08-14 09:41:16Z

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).

Collectives™ on Stack Overflow

How to reverse a linked list using recursion?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related