707.设计链表

707. 设计链表

struct LinkNode{
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val),next(NULL){}
};
//初始化链表
MyLinkedList(){
 	dummyHead=new LinkedNode(0);//虚拟头结点
    size=0;
}
//获取第index个结点数值，index是从0开始的，第0个结点就是头结点
int get(int index){
    if(index>(size-1)||index<0){ //如果index是非法数值返回-1，
        return -1;
    }
    LinkedNode* cur=dummyHead->next;
    while(index){  //当index的值不为0的时候
        cur=cur->next; //continue 到下一个，因为加了个dummy虚拟头节点所以第一个cur->next就是头结点
        index--;
    }
    return cur->val;
}
void addAtHead(int val){
    LinkedNode* newNode=new LinkedNode(val);//创建个的结点
    newNode->next=dummyHead->next;//让新节点的地址指向当初的头节点
    dummyHead->next=newNode; //然后再让虚拟头结点的地址指向新的结点
    size++;
}
//在链表最后面添加一个结点
void addAtTail(int val){
    LinkedNode* newNode =new LinkedNode(val);//创建一个结点
    LinkedNode* cur=dummyHead;//设置一个cur来操作dummy
    while(cur->next!=NULL){//当当前结点不为空的时候 ，继续往下找
        cur=cur->next;
    }
    cur->next=newNode; //把最后一个结点的地址变成newnode
    size++;
}

//在index之前的地方插入新结点
void addIndex(int index,int val){
    if(index>size) return ;// ilegal
    if(index<0) index=0;
    LinkedNode* newNode=new LinkedNode(val); //set new node
    LinkedNode* cur=dummyHead;// set cur 
    while(index){  //index!=NULL
        cur=cur->next; //point to next address
        index--;
    }
    newNode->next=cur->next; //把 newNode的 地址 变成cur地址（后面的值放入） 
    cur->next=newNode;//再把newNode放到cur的地址上（前面的值改变）
    size++;
    
}

//删除第index个结点
void deleteAtIndex(int index){
    if(index>=size||index<0){
        return;
    }
    LinkedNode* cur = dummyHead;
    while(index){
        cur=cur->next;
        index--;
    }
    LinkedNode* tmp =cur->next;
    cur->next=cur->next->next;
    delete tmp;
    size--;
}
//打印链表
void printLinkedList(){
    LinkedNode* cur =dummyHead;
    while(cur->next!=NULL){
        cout<<cur->next->val<<" ";
        cur=cur->next;
    }
    cout<<endl;
}