203、移除链表元素

·虚拟头节点

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/

思路：链表遍历
   | c->next!=NULL
   删除节点
   | c->next=c->next->next;
   c++手动释放内存

代码实现：
     时间复杂度O(n);
     空间复杂度O(1);

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* k=new ListNode(0,head);
        ListNode* c=k;
        while(c->next!=NULL){
            if(c->next->val==val){
                ListNode* d=c->next;
                c->next=c->next->next;//删除节点
                delete d;//释放内存
            }
            else{
                c=c->next;
            }
        }
        head = k->next;
        delete k;
        return head;
    }
};

收获摘要：链表题比较生疏，很少考虑手动释放内存（）

学习的文章链接：https://programmercarl.com/0203.移除链表元素.html#其他语言版本

学习的视频链接：https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

707、设计链表

·就是这题，一下子给我干沉默了orz

题目链接：https://leetcode.cn/problems/design-linked-list/

感悟：越是难啃的题目，感觉收获越多（确信）
   模拟演算的过程真痛苦（泪）
   可以拆成五个小题，它合在一起了

思路：思考链表插入位置，先寻找，然后赋值（顺序是关键）

代码实现：

class MyLinkedList {
public:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
    MyLinkedList() {//初始化
        _size=0;
        head = new ListNode(0);
    }
    
    //寻找第index个节点的值
    int get(int index) {//index节点的数据域，index从0开始算
        if(index<0||index>_size-1)return -1;
        ListNode* cur=head->next;
        while(index>0){
            cur=cur->next;
            index--;
        }
        return cur->val;
    }
    
    //在链表头前面插入val
    void addAtHead(int val) {//在链表头前插入一个节点，成为新的头节点
        ListNode* cur=new ListNode(val,head->next);//虚拟头指向的头节点，链表长度为0时则指向空指针
        head->next=cur;
        _size++;
    }
    
    //在链表尾后插入一个节点
    void addAtTail(int val) {
        ListNode* cur=head;
        while(cur->next!=nullptr){//找到链表尾
            cur=cur->next;
        }
        cur->next=new ListNode(val);//在链表末尾加上
        _size++;
    }
    
    //index长于链表长度时不插入（我直接根据题目描述写了，也可以只分成两种情况）
    void addAtIndex(int index, int val) {
        if(index==_size){//在链表尾后加节点
            addAtTail(val);
        }
        else if(index<=0){//在链表头前加节点
            addAtHead(val);
        }
        else if(index<_size){//在链表中间加节点
            ListNode* cur=head;
            ListNode* add=new ListNode(val);
            while(index>0){
                cur=cur->next;
                index--;
            }
            add->next=cur->next;
            cur->next=add;
            _size++;
        }

    }
    
    void deleteAtIndex(int index) {//删除index节点
        if(index>=0&&index<_size){
            ListNode* cur=head;
            while(index>0){
                cur=cur->next;
                index--;
            }
            ListNode* d=cur->next;
            cur->next=d->next;
            delete d;//释放内存
            _size--;//注意长度减小
        }
    }
    private:
    int _size;
    ListNode* head;//虚拟头节点，指向头节点
};

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

收获摘要：反复看视频，结合图像能对链表的查找、插入有更加清晰的认知。多加练习，还不够熟练。

学习的文章链接：https://programmercarl.com/0707.设计链表.html#代码

学习的视频链接：https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

206、反转链表

·赋值的顺序是关键

我在死循环里迷了路……

题目链接：https://leetcode.cn/problems/reverse-linked-list/submissions/

思路：链表通过指针串联--线性结构
   链表在内存中不连续分布
   改变指针域改变链表方向
   有双指针法和递归法两种

代码实现：（双指针）
     时间复杂度O(n)
     空间复杂度O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=NULL;//直接是空指针
        while(cur!=nullptr){//注意循环边界
            ListNode* k=cur->next;
            cur->next=pre;//反转
            pre=cur;//pre前进
            cur=k;//cur前进,因为前面进行了反转，所以不能=pre，cur应该是k->next
        }
        return pre;//最后pre在链表尾，cur是nullptr,
    }
};

收获摘要：双指针+中间指针，三个指针就像星星在脑袋上旋转doge。有空再试试递归法（递归苦手）

学习的文章链接：https://programmercarl.com/0206.翻转链表.html#双指针法

学习的视频链接：https://www.bilibili.com/video/BV1nB4y1i7eL/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

学习时长：7h（orz)