力扣707

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

题意：

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

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-
• 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);
   */