Advertisement
Guest User

Reverse Singly Linked List using Recursion

a guest
Sep 3rd, 2012
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. struct ListNode
  4. {
  5.     int value;
  6.     ListNode *next;
  7. };
  8.  
  9. class List
  10. {
  11. public:
  12.     List();
  13.     ~List();
  14.     void Append(int newValue);
  15.     void Reverse(); // Reverse list
  16.     void Print();
  17.  
  18. private:
  19.     void AppendNode(ListNode *newNode);
  20.     ListNode *head;
  21. };
  22.  
  23. List::List() : head(0L) {}
  24.  
  25. List::~List()
  26. {
  27.     ListNode *cur = head;
  28.     while (cur != 0L) // 0L is preferred to using NULL, even better
  29.                        // is to use nullptr but not all compilers support it.
  30.     {
  31.         cur = cur->next;
  32.         delete head;
  33.         head = cur;
  34.     }
  35. }
  36.  
  37. void List::Append(int newValue)
  38. {
  39.     ListNode *newNode = new ListNode;
  40.     newNode->value = newValue;
  41.     newNode->next = 0L;
  42.     AppendNode(newNode);
  43. }
  44.  
  45. void List::AppendNode(ListNode *newNode)
  46. {
  47.     if (head != 0L)
  48.     {
  49.         ListNode *cur = head;
  50.         while (cur->next != 0L)
  51.             cur = cur->next;
  52.  
  53.         cur->next = newNode;
  54.     }
  55.     else
  56.     {
  57.         head = newNode;
  58.     }
  59. }
  60.  
  61. void List::Reverse()
  62. {
  63.     if (head != 0L)
  64.     {
  65.         ListNode *hold = head;
  66.         head = head->next;
  67.         Reverse();
  68.         hold->next = 0L;
  69.         AppendNode(hold);
  70.     }
  71. }
  72.  
  73. void List::Print()
  74. {
  75.     ListNode *cur = head;
  76.     while (cur != 0L)
  77.     {
  78.         std::cout << cur->value << ", ";
  79.         cur = cur->next;
  80.     }
  81.     std::cout << std::endl;
  82. }
  83.  
  84. int main()
  85. {
  86.     List l1;
  87.     l1.Append(1);
  88.     l1.Append(2);
  89.     l1.Append(3);
  90.  
  91.     l1.Reverse();
  92.  
  93.     l1.Print();
  94.     return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement