|
1 2 3 4 5 |
/* you're given a double linked list .. reverse it and then print it. * don't use STL's list - use your own implementation. * this is a typical coding interview question! don't say it is simple :) * @auth: AK / AddaxSoft.com */ |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> using namespace std; class node { public: node *next; node *preivous; int data; }; class dlist { private: node *head; public: dlist() { head = 0; } dlist(int data) { head = new node(); head->data = data; head->preivous = head; head->next = 0; } node* gethead() { return head; } void push(int data=0) { if(head == 0) { head = new node(); head->data = data; head->preivous = head; head->next = 0; } else { node *temp = head; while(temp->next != 0) { temp = temp->next; } temp->next = new node(); temp->next->data = data; temp->next->preivous = temp; temp->next->next = 0; } } void print() { if (head == 0) { cout << "empty list"; return; } else { node* tmp = head; while (tmp != 0) { cout << tmp->data << "\t"; tmp = tmp->next; } } } void printrev() { node *tmp = head; while (tmp->next != 0) tmp=tmp->next; while(tmp != head) { cout << tmp->data << "\t"; tmp = tmp->preivous; } cout << tmp->data; } void reverse(node *tmpnode) { if(head == 0 || head->next == 0) return; //if we have no el or 1 el dont reverse. if (tmpnode->next == 0) { tmpnode->next = tmpnode->preivous; head = tmpnode; tmpnode->preivous = head; } else { reverse(tmpnode->next); if (tmpnode->preivous == tmpnode) //if we are at head ONLY after reversing the list. { tmpnode->preivous = tmpnode->next; tmpnode->next = 0; return; } //swap next with previous node* tmp = tmpnode->preivous; tmpnode->preivous = tmpnode->next; tmpnode->next = tmp; } } }; int main() { dlist *dd = new dlist(1); dd->push(2); dd->push(3); dd->push(4); dd->push(5); cout << "printing list: "; dd->print(); cout << "\nprinting in reverse: "; dd->printrev(); cout << "\nreverseing list..."; dd->reverse(dd->gethead()); cout << "\nprinting list: "; dd->print(); cout << "done"; cin.get(); //just to pause the program return 0; } |
Leave a reply