https://leetcode.cn/problems/design-linked-list/description/

<aside> 💡

整体思路：链表有一个虚拟头节点和一个size属性，每次增/删时size对应加/减1，这样size就可以用于遍历链表。链表节点另外定义，包含val和next两个属性。

链表节点结构体：一个val存值，一个next存下个节点地址

链表类：一个size值存当前大小，一个dummyHead虚拟头节点

</aside>

<aside> 💡

处理链表的重点：

• 何时使用虚拟头节点：
  • 需要对链表节点本身进行操作（如增加删除节点等）时使用虚拟头节点
  • 只需要对链表节点内部值进行操作（如查询、修改val等）时可不设置虚拟头节点
• 有虚拟头节点的情况下cur->next可以理解为此时的下标索引：
  • 数组遍历：for(int i=0; i < size; ++i){ cout << myVector[i] }
  • 链表遍历：for(ListNode* cur = dummyHead; cur->next; cur = cur->next){ cout << cur->next->val }
• 链表的边界处理比数组简单：
  • 包含虚拟头节点的情况下，cur->next为空说明到达边界
  • 不包含虚拟头节点时cur为空说明到达边界
  • 可以以0个元素或1个元素的链表作为特例来分析边界是否会溢出 </aside>

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

    MyLinkedList() {
        dummyHead = new ListNode(0);
        size = 0;
    }

    int get(int index) {
        if (index >= 0 && index < size) {
            // i可以优化掉，使用index!=0作为条件，每次执行完--index
            int i = 0;
            ListNode* cur = dummyHead;
            // 循环结束后i一定等于index，即到达索引为index的元素位置
            // 等价于while(index--){ cur = cur->next }
            while (i != index) {
                cur = cur->next;
                ++i;
            }
            return cur->next->val;
        }
        else
            return -1;
    }

    void addAtHead(int val) {
        ListNode* temp = new ListNode(val);
        // 注意顺序，先继承再覆盖
        temp->next = dummyHead->next;
        dummyHead->next = temp;
        ++size;
    }

    void addAtTail(int val) {
        ListNode* cur = dummyHead;
        // 循环结束后cur->next一定指向一个空指针，即到达尾部
        while (cur->next)
            cur = cur->next;
        ListNode* temp = new ListNode(val);
        cur->next = temp;
        ++size;
    }

    void addAtIndex(int index, int val) {
        // 注意index=size的时候也可以添加，此时等价于尾插
        if (index >= 0 && index <= size) {
            ListNode* cur = dummyHead;
            int i = 0;
            while (i != index) {
                cur = cur->next;
                ++i;
            }
            ListNode* temp = new ListNode(val);
            temp->next = cur->next;
            cur->next = temp;
            ++size;
        }
    }

    void deleteAtIndex(int index) {
        if (index >= 0 && index < size) {
            ListNode* cur = dummyHead;
            int i = 0;
            while (i != index) {
                cur = cur->next;
                ++i;
            }
            ListNode* temp = cur->next;
            cur->next = temp->next;
            // 释放内存
            delete temp;
            --size;
        }
    }

    // 打印链表
    void printMyLinkedList() {
        ListNode* cur = dummyHead;
        for (int i = 0; i < size; ++i) {
            std::cout << cur->next->val << ' ';
            cur = cur->next;
        }
        std::cout << std::endl;
    }

    ListNode* dummyHead;
    int size;
};