707.（力扣）设计链表 C++

1、题目描述

理解题目：这道题目设计链表的五个接口

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点

2、设计单链表

（1）这里是单链表的设计

class MyLinkedList {
public:
    //定义链表节点结构体
    struct listNode{
        int val;
        listNode*next;
        listNode(int x):val(x),next(nullptr){}
    };
    //初始化链表
    MyLinkedList() {
       dummyhead=new listNode(0);
       n=0;
    }
    //1、获取链表第index个节点的数值
    int get(int index) {
        if(index>n-1||index<0){
            return -1;
        }
        listNode*cur=dummyhead->next;
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    //2、在链表的最前面插入一个节点（关键在于顺序，或者调换顺序因为头结点可以存住，但是别的地方插入就不行了） 
    void addAtHead(int val) {
        listNode*tmp=new listNode(val);
        //相当于在虚拟头节点和真正的头结点之间插入一个节点，要对它的左右两边都进行改变
        tmp->next=dummyhead->next;//注意顺序
        dummyhead->next=tmp;
        n++;
    }
    //3、在链表的最后面插入一个节点
    void addAtTail(int val) {
        listNode*tmp=new listNode(val);
        listNode*cur=dummyhead;//用到cur是因为比在头结点插入的要多一步找到尾节点的步骤
        //不断遍历，直到找到最后一个节点
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        cur->next=tmp;
        n++;
    }
    //4、在链表第index个节点前面插入一个节点
    void addAtIndex(int index, int val) {
        listNode*tmp=new listNode(val);
        listNode*cur=dummyhead;
        if(index>=0&&index<=n-1){
            while(index--){
            cur=cur->next;
        }
        tmp->next=cur->next;
        cur->next=tmp;
        n++;
        }
        if(index==n){
           addAtTail(val);
        }
}
    //5、删除链表的第index个节点
    void deleteAtIndex(int index) {
        if(index>=0&&index<=n-1){
            listNode*cur=dummyhead;
            while(index--){
                cur=cur->next;
            }
            cur->next=cur->next->next;
            n--;
        }

    }
    private:
    listNode*dummyhead;
    int n;
};

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

（2）在链表的第index个节点前面插入一个节点也可以写为
因为即使是最后一个节点，也有next节点，它的next节点是null

//4、在链表第index个节点前面插入一个节点
    void addAtIndex(int index, int val) {
        listNode*tmp=new listNode(val);
        listNode*cur=dummyhead;
        if(index>=0&&index<=n){
            while(index--){
            cur=cur->next;
        }
        tmp->next=cur->next;
        cur->next=tmp;
        n++;
        }
}

（3）在链表的最前面插入和最后面插入都可以用在Index插入来做

//2、在链表的最前面插入一个节点
    void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //3、在链表的最后面插入一个节点
    void addAtTail(int val) {
        addAtIndex(n,val);
    }