算法刷题Day3 | 203.移除链表元素、707.设计链表、206.反转链表

0 容易被大家忽略的问题
1 移除链表元素
- 1.1 开始的错误解题
- 1.2 头结点和头指针的区别
- - 1.2.1 区别
  - 1.2.2 思考
- 1.3 正确的题解
- - 1.3.1 直接移除法
  - 1.3.2 添加虚拟头节点辅助移除法
  - 1.3.3 总结
2 设计链表
- 2.1 我的解题
3 反转链表
- 3.1 我的解题
- 3.2 其他方法（双指针法、递归写法）

请添加图片描述

🙋‍♂️ 作者：海码007
📜 专栏：算法专栏
💥 标题：算法刷题Day3 | 203.移除链表元素、707.设计链表、206.反转链表
❣️ 寄语：书到用时方恨少，事非经过不知难！

0 容易被大家忽略的问题

为什么一些对链表操作的函数，需要新建一个节点指针然后再去对链表操作呢？

例如写了一个遍历链表的函数，传入head指针。如果我们直接对 head 指针进行操作遍历。就需要 head = head→next 然后遍历下一个节点的值。此时就改变了head的指向，等遍历完之后head就变成一个空指针了，然后你发现操作完链表。

1 移除链表元素

🎈 文档讲解：
🎈 视频讲解：
🎈 做题状态：感觉很挫败，角色很简单的链表删除居然没做出来

1.1 开始的错误解题

其实我最开始的解题问题很大：

头结点的操作和其他节点是不一样的，这一点一开始没有思考到
头结点和头指针没有搞清楚，导致后面移动元素时一团糟。

在这里插入图片描述

1.2 头结点和头指针的区别

1.2.1 区别

在链表中，有两个概念：头结点和头指针。

头结点：
- 头结点是指链表中的第一个实际存储数据的节点。
- 有些链表的设计中会在头部额外添加一个节点，称为头结点，这个节点不存储任何数据，只是为了方便对链表的操作，例如在删除或插入节点时不需要特殊处理头节点的情况。
- 头结点并不一定是链表的第一个元素，它可以位于第一个元素之前，也可以位于第一个元素的位置。
头指针：
- 头指针是指向链表中第一个节点的指针。
- 头指针是为了能够方便地访问链表，它存储了链表的起始地址，通过头指针可以遍历整个链表。
- 在很多情况下，头指针也被用来代表整个链表本身，因此当我们传递链表作为参数时，通常传递的是头指针。

下面是头结点和头指针的示例：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int main() {
    // 创建头结点
    ListNode* head = new ListNode(-1); // 头结点不存储有效数据
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);

    head->next = node1;
    node1->next = node2;

    // 头指针指向链表的第一个节点
    ListNode* headPtr = head;

    // headPtr->next 其实就是 head->next。
    std::cout << "headPtr->next = " << headPtr->next << std::endl;
    std::cout << "head->next =  " << head->next << std::endl;
    
    // 但是 headPtr 指针和 head 头结点的地址是不同的
    std::cout << "&headPtr = " << &headPtr << std::endl;
    std::cout << "&head =  " << &head << std::endl;

    // 释放内存
    delete node2;
    delete node1;
    delete head;

    return 0;
}

在这个示例中，head是头指针，指向链表的第一个节点（头结点）。链表的头结点是一个额外添加的节点，用于简化对链表的操作（添加一个额外的头结点，也被称作虚拟头结点，可以让链表头部元素删除操作和其他元素删除操作保持一致）。

1.2.2 思考

在刚才的代码案例中头指针和头结点的地址是不同的，但是 headPtr->next 和 head->next 是相同的。
head 是指向链表头结点的指针，而 headPtr 是指向head的指针。

1.3 正确的题解

1.3.1 直接移除法

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 直接移除法
        // 1. 先判断头结点是目标节点的情况
        while (head && head->val == val)
        {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 2. 移除非头结点
        ListNode* cur = head;
        while (cur && cur->next)
        {
            if (cur->next->val == val)
            {
                // 创建一个临时指针指向待删除的内存
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

首先通过遍历的方式将头结点是目标元素的值移除完，然后再考虑后序的情况。下面是几个易混淆的值

head->val 是第一个节点的值
head->next 存储的是下一个节点
head->next->val 存储的是下一个节点的值

※※ 然后有个很重要的点需要弄清楚，就是 cur 指针指向的是哪个位置，此时头结点已经全部判断并移除完毕了，可以确定第一个节点肯定不是目标值。那么 cur 指针是从第一个节点开始移动呢？（也就是 ListNode* cur = head->next;）还是从第二个节点开始移动呢？（ListNode* cur = head;）

假如 cur 指针从第二个节点开始移动，那么第二个节点就需要判断自己是不是目标值，然后如果是的话，要将该节点移除。也就是找到当前节点的上个节点，但是我们此时已经找不到上个节点的信息了，因为我们是单向链表，只能一直向后遍历。
假如 cur 指针从第一个节点开始移动，那么就去判断 cur->next->val == val 是否为目标值，如果是的话，那么就将 cur->next = cur->next->next; 此时删除操作就完成了。

在这里插入图片描述

1.3.2 添加虚拟头节点辅助移除法

链表的删除操作，头结点和非头结点是不同的，但是可以通过创建一个虚拟头结点，然后达到头结点和其他节点一样的删除操作。
现在添加了一个新的虚拟头结点，那么此时 cur 指针可以直接指向虚拟头结点，然后判断虚拟头结点的下一个节点是否需要移除（也就是实际存储数据的第一个节点）。

    ListNode* removeElements(ListNode* head, int val)
    {
        // 虚拟头结点法
        // 1. 创建一个虚拟头结点，然后指向第一个节点位置
        ListNode* dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode* cur = dummyNode;

        // 2. 遍历
        while (cur && cur->next)
        {
            if (cur->next->val == val)
            {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else
            {
                cur = cur->next;
            }
        }

        // 3. 返回更新后的头结点指针，注意不是返回head，因为头结点可能被移除，此时因该返回 虚拟头结点指向的下一个节点
        return dummyNode->next;
    }

1.3.3 总结

直接移除法的是分头结点和非头结点两种情况进行操作。（cur 指针从head开始遍历）
虚拟头结点法是在第一个节点前添加一个虚拟头结点，让头结点和非头节点操作保持一致。（cur指针从dummyHead开始遍历）

2 设计链表

🎈 文档讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
🎈 视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
🎈 做题状态：一定要注意虚拟头结点

2.1 我的解题

采用虚拟头结点的方式解题，这样可以保证头结点和非头结点操作的一致性

如下图： cur 是当前指针， dummy 是虚拟头结点，这个节点指向的下一个节点是第一个节点。在解题过程中一定要注意当前指针 cur 指向的是哪里，同时搞清楚当前指针和第一个节点的关系。

【注意】： dummy->next 返回的才是第一个节点，一定要记清楚。

在这里插入图片描述

class MyLinkedList {
public:
    struct LinkNode
    {
        int val;
        LinkNode* next;
        LinkNode(int val) : val(val), next(nullptr) {}
    };

    MyLinkedList() {
        dummyHead = new LinkNode(0);
        size = 0;
    }

    int get(int index) {
        // 如果 index 不在 区间内直接返回-1
        if (index > size - 1 || index < 0) return -1;

        LinkNode* cur = dummyHead->next;
        for (int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkNode* newNode = new LinkNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }

    void addAtTail(int val) {
        LinkNode* cur = dummyHead;
        for (int i = 0; i < size; i++)
        {
            cur = cur->next;
        }
        // 遍历完后，cur指向最后一个节点
        LinkNode* newNode = new LinkNode(val);
        cur->next = newNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        // 当index等于size时，插入链表末尾
        if (index == size)
        {
            addAtTail(val);
            return;
        }
        if (index > size || index < 0) return;

        // 当index是一个有效值时，将新的节点插入index下标之前
        LinkNode* cur = dummyHead;
        while (index > 0)
        {
            cur = cur->next;
            index--;
        }
        // 在cur后面插入新的节点
        LinkNode* newNode = new LinkNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        // 先判断index是否有效
        if (index > size - 1 || index < 0) return;

        LinkNode* cur = dummyHead;
        while (index > 0)
        {
            cur = cur->next;
            index--;
        }
        // 此时cur指向了要删除元素的前一个节点
        LinkNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }

private:
    LinkNode* dummyHead;
    int size;
};

3 反转链表

🎈 文档讲解：
🎈 视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
🎈 做题状态：翻转链表其实就是遍历链表元素，然后插入新链表的头部

3.1 我的解题

注意，reverseHead 是一个虚拟头结点，所以返回的时候是返回 reverseHead->next 。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 翻转链表其实就是遍历链表元素，然后插入新链表的头部
        ListNode* reverseHead = new ListNode(0);
        if (head == nullptr) return head;

        ListNode* cur = head;
        while (cur)
        {
            // 将cur当前的值保存到新链表中
            ListNode* newNode = new ListNode(cur->val);
            newNode->next = reverseHead->next;
            reverseHead->next = newNode;
            cur = cur->next;
        }
        return reverseHead->next;
    }
};

3.2 其他方法（双指针法、递归写法）

双指针法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

递归法

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};