#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;
}
Thursday, April 5, 2012
Reverse Linked List - Recursion - with code
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment