// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 节点的构造函数
};

// Use Custom Constructor
ListNode* head = new ListNode(5);  // 创建一个值为5的头结点

// Use Default Constructor
ListNode* head = new ListNode();
head->val = 5;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_head = new ListNode(0, head);
        ListNode* pre = dummy_head;
        while (pre->next) {
            if (pre->next->val == val) {
                ListNode* tmp = pre->next;
                pre->next = tmp->next;
                delete tmp;
            } else {
                pre = pre->next;
            }
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};

#include <iostream>

struct MyStruct {
    int value;
    void print() {
        std::cout << "Value: " << value << std::endl;
    }
};

int main() {
    MyStruct obj;       // 结构体对象
    obj.value = 10;     // 使用 . 访问成员
    obj.print();        // 使用 . 调用成员函数

    MyStruct* ptr = &obj; // 结构体指针
    ptr->value = 20;      // 使用 -> 访问成员
    ptr->print();         // 使用 -> 调用成员函数

    return 0;
}

#include <iostream>

class MyClass {
public:
    MyClass() { std::cout << "Constructor called\n"; }
    ~MyClass() { std::cout << "Destructor called\n"; }
};

int main() {
    MyClass* obj = new MyClass(); // 动态分配
    delete obj;                  // 释放内存，同时调用析构函数
    return 0;
}

#include <cstdlib>
#include <iostream>

int main() {
    int* arr = (int*)malloc(5 * sizeof(int)); // 动态分配
    if (arr == nullptr) {
        std::cout << "Memory allocation failed\n";
        return 1;
    }
    free(arr); // 释放内存，不涉及析构函数
    return 0;
}

#include <memory>
#include <iostream>

class MyClass {
public:
    MyClass() { std::cout << "Constructor called\n"; }
    ~MyClass() { std::cout << "Destructor called\n"; }
};

int main() {
    std::unique_ptr<MyClass> ptr = std::make_unique<MyClass>(); // 自动管理内存
    // 无需手动 delete，超出作用域时会自动释放内存并调用析构函数
    return 0;
}

class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int val) : val(val), next(nullptr) {}
        ListNode(int val, ListNode* next) : val(val), next(next) {}
    };

    MyLinkedList() {
        _dummy_head = new ListNode(0);
        _size = 0;
    }

    ~MyLinkedList() {
        ListNode* cur = _dummy_head;
        while (cur) {
            ListNode* temp = cur->next;
            delete cur;
            cur = temp;
        }
    }
    
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        ListNode* cur = _dummy_head;
        for (int i = 0; i <= index; i++)    cur = cur->next;
        // while (index--)     cur = cur->next;
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* head = new ListNode(val);
        head->next = _dummy_head->next;
        _dummy_head->next = head;
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode* pre = _dummy_head;
        while (pre->next)   pre=pre->next;
        pre->next = new ListNode(val);
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0; 
        ListNode* pre = _dummy_head;
        for (int i = 0; i < index; i++)    pre = pre->next;
        // while (index--)     pre = pre->next;
        ListNode* cur = new ListNode(val, pre->next);
        pre->next = cur;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        ListNode* pre = _dummy_head;
        for (int i = 0; i < index; i++)    pre = pre->next;
        // while (index--)     pre = pre->next;
        ListNode* tmp = pre->next;
        pre->next = pre->next->next;
        delete tmp;
        //delete命令指示释放了tmp指针原本所指的那部分内存，
        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
        tmp = nullptr;
        _size--;
    }
private:
    int _size;
    ListNode* _dummy_head;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* tmp;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if(!cur) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reverse(cur, tmp);
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        return reverse(pre, cur);
    }
};