一、题目

二、代码

/** * 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                                                      //The first step in building a linked list function 
    {
                                                                          //Regular linked list method definitions
       int val;                                                            //构造函数定义 
       LinkedNode* next;
       LinkedNode(int val):val(val),next(nullptr){
    }
    };

    MyLinkedList()   //自己定义构造函数
    {
    
      _dummyhead= new LinkedNode(0);     //A virtual head node is defined Always point to speculation
      _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;  //Construct a processing node
        int count_index=0;
        while(count_index!=index)
        {
    
            process_node=process_node->next;
            count_index=count_index+1;
        }
        
        // LinkedNode *show_node;
        // show_node=_dummyhead; //Construct a processing node
        // 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)   //Append an element to the head of the linked list
    {
    
        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;  //Construct a processing node

        while(process_node->next!=nullptr)  //先自增 increase all the way to the end point Then jump out at this timewhile
        {
    
          process_node=process_node->next;
        }
       
        process_node->next=temp;    //Set its tail node to betemp 而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会变大 Operations should be made mutually exclusive
    {
    
       int one_operation=0;
  
       std::cout<<"in addAtIndex _size "<<_size<<" "<< std::endl;
        LinkedNode *process_node;
        process_node=_dummyhead;  //Construct a processing node

        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等于链表长度 just add at the end
       {
    

           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 Just insert before the first one 也就是第0Insert after 找到第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;  //Construct a processing node

        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;
      }
    }

    //Don't forget to define private variables
    private:
    int _size;
    LinkedNode* _dummyhead;
};

三、运行结果