Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

Reverse Singly Linked List using Recursion

By: a guest on Sep 3rd, 2012  |  syntax: C++  |  size: 1.33 KB  |  hits: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }