力扣链接

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
 

本题采用虚拟头结点来对链表进行操作，下面给出的代码包含了主函数和完整注释。

#include <iostream>
using namespace std;


class MyLinkedList {
public:
    // 定义一个链表节点的结构体
    struct LinkedNode{
        int val;
        LinkedNode* next;
        // 下面这行是节点的构造函数，使用的是初始化列表的语法，用于初始化一个链表节点的成员变量，同时创建节点的同时直接初始化节点的值
        LinkedNode(int val):val(val),next(nullptr){};
    };
    // 链表类的构造函数 创建一个空的链表，并初始化一个虚拟头结点
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }
    // 获取到第index个节点的值
    int get(int index) {
        if (index > (_size-1) || index <0){
            return -1;
        }
        // 定义一个指针用于遍历整个链表
        LinkedNode* cur = _dummyHead ->next;
        while (index--) {
            cur = cur ->next;
        }
        return cur ->val;
    }
    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        // 定义一个要新插入的节点
        LinkedNode* newNode = new LinkedNode(val);
        // _dummyHead -> next 指的是原始的头结点
        newNode -> next = _dummyHead -> next;
        _dummyHead -> next = newNode;
        _size++;
    }
    // 在链表最后面加入一个节点
    void addAtTail(int val) {
        // 定义一个要新插入的节点
        LinkedNode* newNode = new LinkedNode(val);
        // 定义一个用于遍历链表的指针cur，cur指向当前的虚拟头结点
        LinkedNode* cur = _dummyHead;
        // 使用一个循环，只要下一个节点不是空，cur指针就一直向后移动，直至cur到达最后一个节点
        while (cur -> next != nullptr) {
            cur = cur -> next;
        }
        cur -> next = newNode;
        _size++;
    }
    // 在第index个节点之前插入一个新节点
    void addAtIndex(int index, int val) {
        // 如果index大于链表的长度，则返回空，index可以等于_size，此时说明添加的节点是尾结点
        if (index > _size) return;
        // 如果index小于0，则在头部插入节点
        if (index < 0) index = 0;
        // 定义一个要新插入的节点
        LinkedNode* newNode = new LinkedNode(val);
        // 定义用于遍历链表的指针cur，while用于找到第index个节点的前一个节点
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    // 删除第index个节点
    void deleteAtIndex(int index) {
        // 如果index大于等于链表长度，或者小于0，直接返回
        if (index >= _size || index < 0) {
            return;
        }
        // 定义用于遍历链表的指针cur，while用于找到第index个节点的前一个节点
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        // 用一个临时节点tmp来暂时存储即将删除的这个节点，目的是为了释放它所占用的内存。
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }
    // 打印链表
    void printLinkedList() {
        // 定义一个用于遍历链表的cur指针，初始状态指向虚拟头结点
        LinkedNode *cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val;
            cur = cur->next;
        }
        cout << endl;
    }
private:
    LinkedNode* _dummyHead;
    int _size;
};


int main() {
    MyLinkedList myLinkedList;
    myLinkedList.addAtHead(1);
    myLinkedList.addAtTail(3);
    myLinkedList.addAtIndex(1, 2);
    myLinkedList.printLinkedList(); // 预期输出：1 2 3

    cout << myLinkedList.get(1) << endl; // 预期输出：2

    myLinkedList.deleteAtIndex(1);
    myLinkedList.printLinkedList(); // 预期输出：1 3

    return 0;
}