Thursday, April 5, 2012

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

No comments:

Post a Comment