Reverse Linked List - Recursion - with code

#include <iostream>

using namespace std;

struct node {
        int data;
        struct node *next;
};

typedef struct node NODE;

class linklist {
        private:
                NODE *head;
        public:
                linklist():head(NULL) {}
                void push(int);
                void display();
                void reverse();
                NODE* reverse_driver(NODE*, NODE*);
};

void linklist::push(int data) {
        NODE *tmp = new NODE;
        tmp->data = data;
        tmp->next = NULL;

        if (head == NULL) {
                head = tmp;
        } else {
                NODE *curr = head;
                while (curr->next != NULL) {
                        curr = curr->next;
                }
                curr->next = tmp;
        }
}

void linklist::display() {
        NODE *curr = head;
        cout<<"HEAD: ";
        while (curr != NULL) {
                cout<<curr->data<<"->";
                curr = curr->next;
        }
        cout<<"NULL\n";
}

void linklist::reverse() {
        if (head != NULL) {
                NODE *last = reverse_driver(head, head->next);
                // make the last_node->next to NULL
                head->next = NULL;

                // change the head to the last
                head = last;
        } 
}

NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
        if (nextnode != NULL) {
                NODE *last = reverse_driver(nextnode, nextnode->next);
                nextnode->next = currnode;
                return last;
        } else {
                // Last Node - to be set as Head node
                return currnode;
        }
}

int main () {
        linklist ll;

        ll.push(10);
        ll.push(20);
        ll.push(30);
        ll.push(40);

        ll.display();
        ll.reverse();
        ll.display();
        return 0;
}

The 2-Key Case

About 10 and a half years back, when I was an summer student in IMSC (Institute of Mathematical Science) my mentor(Dr. Venkatesh Raman) asked a question to ponder during my first weekend in the institute and let him know how to solve it.

Before I go into the problem: I will give a background for it.

Predominately, there are 2 problem in Computer Science: Searching and Sorting. "How to do it efficiently ?"

"implicit data structures" - these data structures uses very little or no extra spaces other than the "data elements".

For example, "linked list" which use 1 pointer per "data elements" will amount to the "Space Complexity" of SizeOf(data_elements) + ((Number of data_elements) * SizeOf(Pointer)).

ie.. if the input is N integers, the "Space Complexity" of the integer linked list = N + N (pointers for each integer)
= 2*N

The Space Complexity of a Binary Search Tree (BST) = N + 2 N (2 pointers for each data_element)
= 3*N

But, a Sorted Array is an "Implicit Data Structure", it does not store any extra space. Whereas if you take the "Time Complexity" of both BST and Sorted Array for searching an element in the Collection, it takes same time which is lg(N).

lg = log N to the base 2

Reverse Linked List - Recursion

2 weeks back I was asking someone to write a code for Reversing a Linked List. I just tried one with Recursion:

 #include <iostream>
 
 using namespace std;
 
 struct node {
     int data;
     struct node *next;
 };
 
 typedef struct node NODE;
 
 class linklist {
     private:
         NODE *head;    
     public:
         linklist():head(NULL) {}
         void push(int);
         void display();
         void reverse();
         NODE* reverse_driver(NODE*, NODE*);
 };
 
 void linklist::push(int data) {
     NODE *tmp = new NODE;
     tmp->data = data;
     tmp->next = NULL;
 
     if (head == NULL) {
         head = tmp;
     } else {
         NODE *curr = head;
         while (curr->next != NULL) {
             curr = curr->next;
         }
         curr->next = tmp;
     }
 }
 
 void linklist::display() {
     NODE *curr = head;
     cout<<"HEAD: ";
     while (curr != NULL) {
         cout<<curr->data<<"->";
         curr = curr->next;
     }
     cout<<"NULL\n";
 }
 
 void linklist::reverse() {
     if (head != NULL) {
         NODE *last = reverse_driver(head, head->next);
         // make the last_node->next to NULL
         head->next = NULL;
 
         // change the head to the last
         head = last;
     } 
 }
 
 NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
     if (nextnode != NULL) {
         NODE *last = reverse_driver(nextnode, nextnode->next);
         nextnode->next = currnode;
         return last;
     } else {
         // Last Node - to be set as Head node
         return currnode;
     }
 }
 
 int main () {
     linklist ll;
 
     ll.push(10);
     ll.push(20);
     ll.push(30);
     ll.push(40);
 
     ll.display();
     ll.reverse();
     ll.display();
     return 0;
 }