Day 3 | 203.移除链表元素 707.设计链表 206.反转链表

203.移除链表元素

先贴代码：

ListNode* removeElements(ListNode* head, int val) {
        ListNode* DummyHead = new ListNode(0);
        DummyHead->next = head;
        ListNode* cur = DummyHead;
        while(cur->next != nullptr){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }
        return DummyHead->next;
    }

心得：

? ? ?首先是创建ListNode时候，需要new一个。第二个，刚开始我弄混了 cur->next 和 tmp，我错以为是这俩个指针同时指向要被删除的值 val，但是细想一下，在最开始，我先用tmp指向了被删除的链表，接着用 cur->next 指向了下一个删除后的链表，所以 cur->next 已经跟要被删除的链表无关了，所以只有 tmp 指向要删除列表，则只需要 delete tmp 即可做到释放要被删除的链表元素。? ?

class MyLinkedList {
public:
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(nullptr) {}
};
    MyLinkedList() {
        DummyNode_ = new ListNode(0);
        size_ = 0;
    }
    
    int get(int index) {
        if(index >(size_-1) || index < 0) return -1;
        ListNode* cur = DummyNode_;
        while(index >= 0){
            cur = cur->next;
            index--;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* NewNode = new ListNode(val);
        NewNode->next = DummyNode_->next;
        DummyNode_->next = NewNode;
        size_++;
    }
    
    void addAtTail(int val) {
        ListNode* NewNode = new ListNode(val);
        ListNode* cur = DummyNode_;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = NewNode;
        size_++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size_) return; // void 直接 return 就好
        if(index < 0) index = 0;
        ListNode* cur = DummyNode_;
        while(index--){
            cur = cur->next;
        }
        ListNode* NewNode = new ListNode(val);
        NewNode->next = cur->next;
        cur->next = NewNode;
        size_++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= size_ || index < 0) return;
        ListNode* cur = DummyNode_;
        while(index--){
            cur = cur->next;
        }
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size_--;
    }
private:
    int size_ ;
    ListNode* DummyNode_; 

心得：

首先得明白初始化一个链表我需要什么信息？一个就是头指针，我们用虚拟头指针来代替，另一个就是链表长度。

还有个小失误就是对链表该动时候没有对 size 进行调整，导致出了最多的问题，以及?while(index--)，这个当 index = 0的时候是不会运行的，省去了我单独给 Index = 0 处理的步骤，这个我之前还分开写了，属实没必要。

 ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

心得：我最开始 pre 写的是 pre = new ListNode()，这样其实她并不是指的是一个 nullptr，而是一个val = 0的指针，所以一开始就要给他定义为NULL，不然一开始给他翻转的时候，他其实是有值的，不能作为末尾的nullptr。