一:题目

在这里插入图片描述

二:上码

class MyLinkedList {
public:

    //定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        node = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

  
    //根据示例我们可以得出下标为0的是第一个数值
    int get(int index) {
        if(index > _size - 1 || index < 0){//链表数值范围[0,_size-1]
            return -1;
        }   
        LinkedNode *temp = node->next;
        while(index--){//这个index--,可以让我们知道指针往后移动的次数，直到为0找到为止
            temp = temp->next;
        }
        return temp->val;
    }
    
    //插入一个新结点 为头节点
    void addAtHead(int val) {
        LinkedNode*newNode = new LinkedNode(val);
        newNode->next = node->next;
        node->next = newNode;
        _size++;
    }    
    //在尾部插入一个结点
    void addAtTail(int val) {
        LinkedNode *newNode = new LinkedNode(val);
        
        LinkedNode* temp = node;
        while(temp->next != NULL){
            temp = temp->next;
        }
        temp->next = newNode;
        _size++;
    }
    
    //第一种情况:比如(1,2) 则在第二个元素的位置插入2
    //如果index等于链表长度则在结尾插入一个值
    //如果大于链表的长度则返回空
    
    void addAtIndex(int index, int val) {
        if(index > _size){
            return;
        }

        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* temp = node;//第一个结点是虚拟结点
        
        //比如 原来的链表为1->3  然后插入(1,2) 因为有虚拟结点的存在所以
        //链表实际为(0->1->3)  所以当index为0的时候 temp 指向是链表中的1
        while(index--){
            temp = temp->next;
        }

        newNode->next = temp->next;
        temp->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index > _size-1)//大于链表的长度
            return ;

        LinkedNode* temp = node;
        while(index--){
            temp = temp->next;
        }
        //当结束while循环的时候  这时候的temp指向的是要删除结点的前一个结点
        
        LinkedNode *cmp = temp->next;//cmp指向了要删除的结点
        temp->next = temp->next->next;
        delete cmp;
        _size--;


    }

    private:
    int _size;
    LinkedNode * node;
};

/**
 * 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);
 */