链表理论基础

建议：了解一下链接基础，以及链表和数组的区别

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

建议： 本题最关键是要理解 虚拟头结点的使用技巧，这个对链表题目很重要。
题目链接：203. 移除链表元素 - 力扣（LeetCode）
题目链接/文章讲解/视频讲解：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.设计链表

建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode *next;
        LinkedNode(int x):val(x),next(NULL){}
    };

    MyLinkedList() {
        _dummyhead=new LinkedNode(0);
        _size=0;
    }
    
    int get(int index) {
        //LinkedNode* cur = _dummyhead->next;
        //int n=0;
        //while(cur!=NULL){
        //    if(n==index){
        //        return cur->val;
        //    }
        //    else{
        //        n++;
        //        cur=cur->next;
        //    }
        //}
        //return -1;

        LinkedNode *cur=_dummyhead->next;
        if(index>(_size-1)||index<0){
            return -1;
        }
        while(index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* node=new LinkedNode(val);
        node->next=_dummyhead->next;
        _dummyhead->next=node;
        _size++;//第一次没写这句

        //struct LinkedNode node = new LinkedNode(val);//
        //node.next =_dummyhead->next;
        //_dummyhead->next=node;
    }
    
    void addAtTail(int val) {
        //LinkedNode *cur=_dummyhead->next; //第一次这里写错了
        LinkedNode *cur=_dummyhead;
        LinkedNode *newnode=new LinkedNode(val);
        while(cur->next!=NULL){
            //cur->next=cur->next->next; //实际写下面那个就可以
            cur=cur->next;
        }
        cur->next=newnode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        LinkedNode *newnode=new LinkedNode(val);
        LinkedNode *cur=_dummyhead;
        
        if(index>_size){
            return;
        }
        else if(index==_size){
            while(cur->next!=NULL){
                cur=cur->next;
            }
            cur->next=newnode;
        }
        else{
            while(index--){
                //cur->next=cur->next->next;
                cur=cur->next;
            }
            newnode->next=cur->next;
            cur->next=newnode;
        }
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>=_size){
            return;
        }
        LinkedNode *cur=_dummyhead;
        while(index--){
            cur=cur->next;
        }
        LinkedNode *tmp=cur->next;
        cur->next=cur->next->next;
        delete(tmp);
        tmp=nullptr;
        //if(index==0){
        //    delete(cur); //这里也忘记节点删除方法了，需要先保存原地址
        //}
        //while(--index){
        //    cur->next=cur->next->next;
        //}//若cur定义为头节点（_dummyhead->next）而不是虚拟头节点（_dummyhead），那么下面while我写--index，这样就会有当index为0，while里面的值是-1的问题，就还得单独判断cur是否指向空，解法上来说就不够统一，还需要单独判断这种情况
        _size--;
    }

private:
    LinkedNode* _dummyhead;
    int _size;
};

/**
 * 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);
 */

206.反转链表

建议先看我的视频讲解，视频讲解中对 反转链表需要注意的点讲的很清晰了，看完之后大家的疑惑基本都解决了。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

今日感受：

周五只想玩。。只做了第一个，剩下两个明天继续，还得补一下第二天的螺旋矩阵，啊。。
但是今天也敲了，不错，继续努力。。

今日时长：