#include <iostream>
#include <vector>

using namespace std;

// why struct rather than class?
// usually structs are used for simpler things even
// though you can define functions withins structs too
// difference: in structs, everything is public by default
// in classes, everything is private by default
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int val) : val(val), next(nullptr) {}
};

// when creating a new node you need to allocate memory storage for it
// ListNode* head = ListNode(0);
// head points nowhere, since ListNode(0) is not stored. ListNode(0) is automatically destroyed.
// ListNode node(0);
// head = &node;
// new solves this issue:
// ListNode* head = new ListNode(0);
ListNode* vec2list(const std::vector<int>& vec) {

    if (vec.empty())
        return nullptr;

    ListNode* head = new ListNode(vec[0]);
    ListNode* current = head;

    for (int i = 1; i < vec.size(); ++i) {
        ListNode* next = new ListNode(vec[i]);
        current->next = next;
        current = current->next;
    }

    return head;
}

void printLinkedList(ListNode* head) {

    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

void deleteNode (ListNode* head, int num) {

    ListNode* current = head;
    ListNode* prev = nullptr;

    int i = 0;
    while (current) {
        if (i == num) {
            prev->next = current->next;
            delete current;
            break;
        }
        prev = current;
        current = current->next;
        ++i;
    }
}

// Run-time complexity O(1)
void deleteNode (ListNode* current) {

    ListNode* next = current->next;

    current->val = next->val;
    current->next = next->next;
    delete next;

}

ListNode* reverseList(ListNode* head) {

    ListNode* prev = nullptr;
    ListNode* current = head;
    ListNode* next = nullptr;

    while(current) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head = prev;

    return head;
}

int main(){

    ListNode my_list_node(5);

    std::vector<int> my_vec_of_ints = {1,2,3,4,5,6};

    ListNode* my_linked_list = vec2linkedlist(my_vec_of_ints);

    printLinkedList(my_linked_list);

    deleteNode(my_linked_list, 2);

    printLinkedList(my_linked_list);

    deleteNode2(my_linked_list->next->next);

    printLinkedList(my_linked_list);

    my_linked_list = reverseList(my_linked_list);

    printLinkedList(my_linked_list);

    return 0;
}