力扣707

力���题目链接(opens new window)

题意：

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

  使用虚拟头节点统一操作，

  遍历链表的指针的起始处根据不同的操作有不同的设置，

   

  class MyLinkedList {public:    struct LinkNode{        int val;        LinkNode * next;        LinkNode(int val):val(val),next(nullptr){}    };    MyLinkedList() {       dumHead = new LinkNode(0);       size = 0;    }        int get(int index) {        if(index  (size - 1)){            return -1;        }        LinkNode * p = dumHead->next;//遍历链表得指针指向虚拟头节点的下一个结点        while(index--){            p=p->next;        }        return p->val;    }        void addAtHead(int val) {        LinkNode * s= new LinkNode(val);        s->next = dumHead->next;//遍历链表得指针指向虚拟头节点的下一个结点        dumHead->next = s;        size++;//这里链表长度要加1    }        void addAtTail(int val) {        LinkNode * s = new LinkNode(val);        LinkNode*p=dumHead;//遍历链表得指针指向虚拟头节点        while(p->next!=nullptr){            p=p->next;        }        p->next = s;        size++;//链表长度加一    }        void addAtIndex(int index, int val) {        if(index>size)return;        if(indexnext;//p指向index结点的前一个结点            }            s->next = p->next;            p->next = s;            size++;    }        void deleteAtIndex(int index) {       if (index >= size || index next;//cur的next指向的要删除的结点，即第n个        }        LinkNode* tmp = cur->next;        cur->next = cur->next->next;        delete tmp;        //delete命令指示释放了tmp指针原本所指的那部分内存，        //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针        //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间        tmp=nullptr;        size--;    }    private:        int size;        LinkNode* dumHead;};/** * 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); */