一、题目

二、代码

/** * 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); */
class MyLinkedList {
    
public:
    
    struct LinkedNode                                                      //构建链表功能函数第一步 
    {
                                                                          //常规链表方法定义
       int val;                                                            //构造函数定义 
       LinkedNode* next;
       LinkedNode(int val):val(val),next(nullptr){
    }
    };

    MyLinkedList()   //自己定义构造函数
    {
    
      _dummyhead= new LinkedNode(0);     //定义了一个虚拟的头结点 永远指向投机诶单
      _size =0;

    }

    int get(int index) 
    {
    
       if(index>=0&&index<=_size-1)
       {
    
        //std::cout<<"in get _size "<<_size<<" "<< std::endl;

        LinkedNode *process_node;
        process_node=_dummyhead;  //构造处理节点
        int count_index=0;
        while(count_index!=index)
        {
    
            process_node=process_node->next;
            count_index=count_index+1;
        }
        
        // LinkedNode *show_node;
        // show_node=_dummyhead; //构造处理节点
        // while(show_node->next!=nullptr)
        // {
    
        // std::cout<<" "<<show_node->val<<" ";
        // show_node=show_node->next;
        // }
        // std::cout<<" "<<show_node->val<<" "; //打印最后一个
        // std::cout<<" "<< std::endl;
        // std::cout<<"_size "<<_size<<" "<< std::endl;


        return process_node->next->val;
       }

       else 
       {
    
           return -1;
       }
    }
    
    void addAtHead(int val)   //在链表头追加元素
    {
    
        LinkedNode *temp;
        temp=new LinkedNode(val);  //构造该节点
        temp->next=_dummyhead->next;
        _dummyhead->next=temp;
        _size+=1;
        
    }
    
    void addAtTail(int val)   //在链表末尾追加元素
    {
    
            // LinkedNode *show_node;
            // show_node=_dummyhead; //构造显示节点
            // while(show_node->next!=nullptr)
            // {
    
            // std::cout<<" "<<show_node->val<<" ";
            // show_node=show_node->next;
            // }
            // std::cout<<" "<<show_node->val<<" "; //打印最后一个
            // std::cout<<" "<< std::endl;
            // std::cout<<"in tail _size "<<_size<<" "<< std::endl;

        LinkedNode *temp;
        temp=new LinkedNode(val);  //构造该节点

        LinkedNode *process_node;
        process_node=_dummyhead;  //构造处理节点

        while(process_node->next!=nullptr)  //先自增 一直增加到尾结点 那么这时候跳出while
        {
    
          process_node=process_node->next;
        }
       
        process_node->next=temp;    //将其尾节点设置成为temp 而temp本身指向nullptr 不用操作
        _size+=1;                    //大小加1

            // show_node=_dummyhead; //构造显示节点
            // while(show_node->next!=nullptr)
            // {
    
            // std::cout<<" "<<show_node->val<<" ";
            // show_node=show_node->next;
            // }
            // std::cout<<" "<<show_node->val<<" "; //打印最后一个
            // std::cout<<" "<< std::endl;
            // std::cout<<"out tail _size "<<_size<<" "<< std::endl;

    }
    
    void addAtIndex(int index, int val)    //注意 操作之后_size会变大 应该让操作互斥
    {
    
       int one_operation=0;
  
       std::cout<<"in addAtIndex _size "<<_size<<" "<< std::endl;
        LinkedNode *process_node;
        process_node=_dummyhead;  //构造处理节点

        LinkedNode *temp;
        temp=new LinkedNode(val);  //构造该节点

       if(index<0&&one_operation==0)  //如果索引值小于0
       {
    

          addAtHead(val);
          one_operation=1;
       }
       if(index==_size&&one_operation==0)  //如果index等于链表长度 就加在末尾
       {
    

           addAtTail(val);
           one_operation=1;
       }
     
       if(index>_size&&one_operation==0)  //如果index大于链表长度 就不插入
       {
    
        
          //no operation 
          one_operation=1; 
       }

        std::cout<<"in addAtIndex _size "<<_size<<" "<< std::endl;

       if(index>=0&&index<_size&&one_operation==0)
       {
    
          if(index==0)  addAtHead(val);
          else
          {
    
               int count_index=0;
               while(count_index!=index)                         //如果index等于1 就是在第一个之前插入 也就是第0个之后插入 找到第0个就可以了 
               {
    
                 process_node=process_node->next;  
                 count_index=count_index+1;
               }
               temp->next=process_node->next;
               process_node->next=temp;
               _size+=1;                    //大小加1
          }
          one_operation=1;
       }

      std::cout<<"out addAtIndex _size "<<_size<<" "<< std::endl;
    }
    
    void deleteAtIndex(int index)
    {
    
      if(index<=_size-1&&index>=0)
      {
    
        LinkedNode *process_node;
        process_node=_dummyhead;  //构造处理节点

        LinkedNode *temp;
        temp=new LinkedNode(0);  //构造该节点

        int count_index=0;
        while(count_index!=index)
        {
    
            process_node=process_node->next;
            count_index=count_index+1;
        }
        temp=process_node->next;
        process_node->next=process_node->next->next;
        delete temp;
        _size-=1;
      }
    }

    //私有变量不要忘了定义
    private:
    int _size;
    LinkedNode* _dummyhead;
};

三、运行结果