链表题目复习Day3

203移除链表元素

设置虚拟头节点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        dummy->next = head;
        while(cur!=nullptr&&cur->next!=nullptr){
            if(cur->next->val==val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else{
                cur = cur->next;
            }
            
            
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

这里面容易犯错的地方：

• 虚拟节点要new出来，否则就是野指针

• 一定要再定义一个cur，用来遍历

  • 不能使用head：head会跑走，最后返回的dummy->next不是头节点
  • 一定要赋成dummy：统一操作，万一头节点也是需要删除的呢

• while当中要对当前和下一个都进行判空，一定一定不能去操作空指针

• while当中必须是一个if…else…的结构，两个是对立的操作，虽然当前删除了cur->next，但是有可能现在指向的cur->next依然与目标值相等，所以每次都需要判断，是目标值就进if，不是目标值就进else

• 一定要一直记得是利用上一个节点去删除目标值，因为是单链表

• 最后返回也必须是dummy->next，因为有可能head节点被删除了；要是想防止内存泄漏，把dummy->next重新赋值回head，返回head即可

• 存在内存泄漏，C++要记得释放不用的指针

不设置虚拟头节点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head!=nullptr&&head->val==val){
            head = head->next;
        }
        ListNode* cur = head;
        while(cur!=nullptr&&cur->next!=nullptr){
            if(cur->next->val==val){
                cur->next = cur->next->next;
            }
            else{
                cur = cur->next;
            }
        }
        return head;
    }
};

时长：30min

看视频：15min

重新手撕：15~20min

必须熟悉！设计链表

哇去，真的好多东西都要考虑到！这个必须要多刷几遍熟悉熟悉，而且一定好好记录错误点

设计链表需要完成以下内容：

• 构造节点：val next 节点的构造函数 构造节点一定要写在所有使用节点的前面，不然会报错
• 链表初始化：虚拟头节点 链表长度
• 初始化的成员函数：虚拟头节点 链表长度 这俩一定是要写在类内链表初始化之外的(别和节点的构造弄混了)，可私有化，更安全
• 可以再写一个析构函数防止内存泄漏

实现增删改查：

• 增：添加节点。要有节点位置(一般称为第n个节点前增加节点)

一般链表默认头节点为第零个节点，插入节点轮询n次后正好就到了第n-1个节点，方便去操作第n个节点

还需要回看代码随想录当中的代码！！！

class MyLinkedList {
public:
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int x):val(x), next(nullptr){}
    };
    MyLinkedList() {
        dummy = new ListNode(0);
        sized = 0;
    }
    ~MyLinkedList() {
        delete dummy;
    }
    int get(int index) {
        ListNode* cur = dummy->next;//这里不能是虚拟节点，因为当前节点就要是能返回正确值的
        if(index>(sized-1)||index<0){
            return -1;
        }
        while(index--){
            cur = cur->next;
        }
        return cur->val;//注意这里是获取值
    }
    
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = dummy->next;//不能直接写head
        dummy->next = newNode;
        sized++;
    }
    
    void addAtTail(int val) {
        ListNode* cur = dummy;
        while(cur->next!=nullptr){
            cur = cur->next;
        }
        cur->next = new ListNode(val);
        sized++;
    }
    
    void addAtIndex(int index, int val) {
        ListNode* cur = dummy;
        if(index>sized||index<0){//这里等于是sized可以插入的!
            return;
        }
        while(index--){
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        sized++;
    }
    
    void deleteAtIndex(int index) {
        ListNode* cur = dummy;
        if(index>sized-1||index<0){
            return;
        }
        while(index--){
            cur = cur->next;
        }
        cur->next = cur->next->next;
        sized--;
    }
private:
    ListNode* dummy;
    int sized;
};

206反转链表

双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //双指针思想
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* temp = cur->next;//存下一个节点
            cur->next = pre;//在这步之前，必须要提前存好cur的next不然就断了，绝对不能写错成这样啊pre = cur->next
            pre = cur;
            cur = temp;
        } 
        return pre;
    }
};

虽然一开始想到了用双指针，但是不知道应该怎么指，谁指谁

易错点：

• 一定要有一个临时指针去存一下cur在链表的下一个节点
• 在移动的时候，一定是pre先走，然后cur再走，因为cur先走，pre和cur指向的是同一个了
• ①cur->next = pre;②pre = cur->next;是两个东西！！！①是改变cur的next指针域的指向为pre②是将cur的next节点赋值成pre，在这里的意思就是pre和temp都指向了同一个位置了，所以差别很大的！！！

递归法

class Solution {
public:
    ListNode* myReverse(ListNode* pre, ListNode* cur){
        if(cur==nullptr) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return myReverse(cur, temp);
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        return myReverse(pre, head);
    }
};

学习完双指针法，再回来看递归法，简直太简单了吧！