#include <iostream>
#include <stdexcept>

using namespace std;

template <class T>
class SinglyLinkedList {
   private:
    class Node {
       public:
        Node* next;
        T data;

        Node(T data, Node* next) {
            this->data = data;
            this->next = next;
        }

        ~Node() {
            if (this->next != nullptr) {
                delete this->next;
            }
        }
    };

    Node* head;
    int length;

   public:
    SinglyLinkedList() {
        this->head = nullptr;
        this->length = 0;
    }

    ~SinglyLinkedList() { delete this->head; }

    int size() { return this->length; }

    void display() {
        for (Node* node = this->head; node != nullptr; node = node->next) {
            cout << node->data << " -> ";
        }
        cout << "Ø" << endl;
    }

    void prepend(T data) {
        this->head = new Node(data, this->head);
        this->length += 1;
    }

    void reverse() {
      /* þurfum 3 hnútabreytur, eina fyrir þann sem við ætlum að breyta next á,
         eina fyrir hnútinn á undan og eina fyrir hnútinn á eftir */
      Node* a = this->head->next; //O
      Node* b = this->head->next; //O
      Node* c = this->head; //T

      c->next = nullptr; //hausinn verður halinn

      for (int i=0; i<this->length-2; i++) { //-2 vegna þess að við stillum hausinn og halann útfyrir
        a = a->next; //L, 2... //geymum hnútinn á eftir til að nota í næstu ítrun
        b->next = c; //T, O... //breytum vísun hnúts í hnútinn á undan
        //stillingar fyrir næstu ítrun:
        c = b; //O, L...
        b = a; //L, 2...
      }
      //stillum hausinn:
      this->head = a;
      this->head->next = c;
    }
};

int main() {
    // Skilgreining lista sem inniheldur tákn
    SinglyLinkedList<char> list;
    list.prepend('G');
    list.prepend('3');
    list.prepend('0');
    list.prepend('2');
    list.prepend('L');
    list.prepend('O');
    list.prepend('T');

    list.display();

    list.reverse();

    list.display();

    return 0;
}