鏈表理論基礎(chǔ)

建議：了解一下鏈接基礎(chǔ)抡柿，以及鏈表和數(shù)組的區(qū)別

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

203.移除鏈表元素

建議： 本題最關(guān)鍵是要理解 虛擬頭結(jié)點(diǎn)的使用技巧，這個(gè)對(duì)鏈表題目很重要等恐。
題目鏈接：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.設(shè)計(jì)鏈表

建議： 這是一道考察 鏈表綜合操作的題目洲劣，不算容易备蚓，可以練一練 使用虛擬頭結(jié)點(diǎn)

題目鏈接/文章講解/視頻講解：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++;//第一次沒(méi)寫這句

        //struct LinkedNode node = new LinkedNode(val);//
        //node.next =_dummyhead->next;
        //_dummyhead->next=node;
    }
    
    void addAtTail(int val) {
        //LinkedNode *cur=_dummyhead->next; //第一次這里寫錯(cuò)了
        LinkedNode *cur=_dummyhead;
        LinkedNode *newnode=new LinkedNode(val);
        while(cur->next!=NULL){
            //cur->next=cur->next->next; //實(shí)際寫下面那個(gè)就可以
            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); //這里也忘記節(jié)點(diǎn)刪除方法了，需要先保存原地址
        //}
        //while(--index){
        //    cur->next=cur->next->next;
        //}//若cur定義為頭節(jié)點(diǎn)（_dummyhead->next）而不是虛擬頭節(jié)點(diǎn)（_dummyhead）囱稽，那么下面while我寫--index郊尝，這樣就會(huì)有當(dāng)index為0，while里面的值是-1的問(wèn)題战惊，就還得單獨(dú)判斷cur是否指向空流昏，解法上來(lái)說(shuō)就不夠統(tǒng)一，還需要單獨(dú)判斷這種情況
        _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.反轉(zhuǎn)鏈表

建議先看我的視頻講解吞获，視頻講解中對(duì) 反轉(zhuǎn)鏈表需要注意的點(diǎn)講的很清晰了况凉，看完之后大家的疑惑基本都解決了。

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

今日感受：

周五只想玩各拷。刁绒。只做了第一個(gè)，剩下兩個(gè)明天繼續(xù)撤逢，還得補(bǔ)一下第二天的螺旋矩陣膛锭，啊。蚊荣。
但是今天也敲了初狰，不錯(cuò)，繼續(xù)努力互例。奢入。

今日時(shí)長(zhǎng)：