Question

Consider the following definition of a doubly linked-list:

class LinkedList{
        public:
                LinkedList():head(0), tail(0){}
                ~LinkedList();
                void reverse(); 
                //reverses the order of elements in the linked list
                void insert(int value);
        private:
            struct Node{
                        int data;
                        Node* next;
                        Node* prev;
                };
                Node* head;
                Node* tail;
                //Add your helper function here that recursively reverses the order of elements in the linked list


};

Write the declaration of a helper function in the class provided above that recursively reverses the order of elements in the linked list. This function will be used by the reverse() method. Then, write the implementation of both the reverse() method and the helper function.

Answer 1

// C++ program to reverse the elements of the LinkedList

#include <iostream>

using namespace std;

class LinkedList{

        public:

                LinkedList():head(0), tail(0){} // default contructor to create an empty linked list

                ~LinkedList(); // destructor to delete the elements of the linked list

                void reverse(); //reverses the order of elements in the linked list

                void insert(int value); // insert an element at the end of the linked list

                void print(); // print the elements of the linked list

        private:

            struct Node{

                        int data;

                        Node* next;

                        Node* prev;

                };

                Node* head;

                Node* tail;

                void reverse(Node *node); // helper function to reverse the linked list recursively

};

LinkedList::~LinkedList()

{

       // loop that continues till we reach the end of the linked list

       while(head != NULL)

       {

             Node *temp = head;

             head = head->next;

             delete(temp); // delete the previous head element

       }

       tail = NULL; // set tail to NULL

}

void LinkedList::insert(int value)

{

       Node *node = new Node;

       node->data = value;

       node->prev = NULL;

       node->next = NULL;

       if(head == NULL) // empty list, insert the value at the front

       {

             head = node;

             tail = node;

       }else // insert the value at the end

       {

             tail->next = node;

             node->prev = tail;

             tail = node;

       }

}

void LinkedList::print()

{

       if(head == NULL) // empty list

       {

             cout<<"Empty list"<<endl;

       }else

       {

             Node *curr = head;

             // loop to print the elements of the linked list

             while(curr != NULL)

             {

                    cout<<curr->data<<" ";

                    curr = curr->next;

             }

             cout<<endl;

       }

}

void LinkedList::reverse()

{

       reverse(head); // call the helper function

       // swap head and tail

       Node *temp = head;

       head = tail;

       tail = temp;

}

void LinkedList::reverse(Node *node)

{

       if(node != NULL) // if node is not null

       {

             // swap the next and prev pointers of the node

             Node *temp = node->next;

             node->next = node->prev;

             node->prev = temp;

             reverse(node->prev); // call the helper function to reverse the previous node

       }

}

int main() {

       // test the functions of the LinkedList class

       LinkedList list;

       // insert elements to list

       for(int i=1;i<=10;i++)

             list.insert(i);

       cout<<"Original List : "<<endl;

       list.print(); // print the original list

       // reverse the list

       list.reverse();

       // print the reversed list

       cout<<"Reversed List : "<<endl;

       list.print();

       return 0;

}

//end of program

Output: