Monday, April 2, 2012

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:

  0 #include <iostream>
1
2 using namespace std;
3
4 struct node {
5 int data;
6 struct node *next;
7 };
8
9 typedef struct node NODE;
10
11 class linklist {
12 private:
13 NODE *head;
14 public:
15 linklist():head(NULL) {}
16 void push(int);
17 void display();
18 void reverse();
19 NODE* reverse_driver(NODE*, NODE*);
20 };
21
22 void linklist::push(int data) {
23 NODE *tmp = new NODE;
24 tmp->data = data;
25 tmp->next = NULL;
26
27 if (head == NULL) {
28 head = tmp;
29 } else {
30 NODE *curr = head;
31 while (curr->next != NULL) {
32 curr = curr->next;
33 }
34 curr->next = tmp;
35 }
36 }
37
38 void linklist::display() {
39 NODE *curr = head;
40 cout<<"HEAD: ";
41 while (curr != NULL) {
42 cout<<curr->data<<"->";
43 curr = curr->next;
44 }
45 cout<<"NULL\n";
46 }
47
48 void linklist::reverse() {
49 if (head != NULL) {
50 NODE *last = reverse_driver(head, head->next);
51 // make the last_node->next to NULL
52 head->next = NULL;
53
54 // change the head to the last
55 head = last;
56 }
57 }
58
59 NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
60 if (nextnode != NULL) {
61 NODE *last = reverse_driver(nextnode, nextnode->next);
62 nextnode->next = currnode;
63 return last;
64 } else {
65 // Last Node - to be set as Head node
66 return currnode;
67 }
68 }
69
70 int main () {
71 linklist ll;
72
73 ll.push(10);
74 ll.push(20);
75 ll.push(30);
76 ll.push(40);
77
78 ll.display();
79 ll.reverse();
80 ll.display();
81 return 0;
82 }
83

No comments:

Post a Comment