算法入门打卡Day3
今日收获
- 链表的概念
- 链表的基础操作以及如何设计一个自己的链表
- 反转链表（双指针法、递归法（重点！！））
- NULL和nullptr的区别
学习时间：6h
正文
链表的概念
和数组不同，链表是通过指针将不连续的内存空间里的数据串联起来，于是删除与增加元素变得更加轻松。
以下是一个普通单链表的定义方式：
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数//重温一下，构造函数的函数名和结构体/类名相同，前面没有返回值类型，形参列表之后由冒号开始是初始化列表，各变量以逗号分隔，跟随的括号内是初始化的值。
};
这是通过结构体实现的。这里要注意，如果不自己定义构造函数的话，初始化新节点时会多出一步，如下：
ListNode* head = new ListNode();
head->val = 5;
链表的最后一个节点next指针指向的是nullptr，即空指针。
移除链表元素
LeetCode203
题目：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
分析：
删除节点时，让前一个节点的next指针指向下一个节点，并一定要记得释放被删除节点的堆内存！
在释放内存这一步，因为我们需要在next的指向被改变后访问到被删除节点的下一个节点（这需要利用到被删除节点的next指针），所以我们可以使用一个临时指针temp储存地址，在完成重新指向后再释放temp。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点while (head != NULL && head->val == val) { // 注意这里不是if，这样就可以连续删除符合条件的头节点ListNode* tmp = head;head = head->next;delete tmp;}// 删除非头结点，此时头节点一定不是满足条件的ListNode* cur = head;while (cur != NULL && cur->next!= NULL) { //因为要指向下一个节点的下一个节点，所以下一个节点不能为空if (cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;} else {cur = cur->next;}}return head;}
};
这个小箭头->直观好用，表示该指针指向对象中的某个元素，
如cur->next表示当前的（current）指针指向的对象（某个类型为ListNode的节点）中的next指针。
但是即便如此我们还不够满意，因为我们需要将头节点和非头节点分开来讨论，写起来太多了，于是我们可以利用的是虚拟头节点（dummyHead）。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点,注意结构体/类中定义了有参构造函数就不提供默认无参了，所以在这里还是给了一个参数0dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作ListNode* cur = dummyHead;while (cur->next != NULL) {if(cur->next->val == val) {ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;} else {cur = cur->next;}}head = dummyHead->next; //此时head最初指向的内存空间可能在过程中被释放了，现在我们重新让head指向头节点delete dummyHead; //释放虚拟头节点return head;}
};
设计链表
LeetCode707
设计并实现自己的链表。
链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点_size = 0;}// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}LinkedNode* cur = _dummyHead->next;while(index--){ // 如果--index 就会陷入死循环cur = cur->next;}return cur->val;}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0; LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--) {cur = cur ->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;//delete命令指示释放了tmp指针原本所指的那部分内存，//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间tmp=nullptr;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;};
- 在设计我的链表的过程中，我一开始没有搞清楚这个类和结构体的嵌套，把
LinkedNode和MyLinkedList搞混了。MyLinkedList在这里是链表的类，里面包含了链表的长度_size、虚拟头节点_dummyHead、链表节点的结构体LinkedNode、初始化构造函数。而LinkedNode中包含节点储存的值、next指针、初始化构造函数。 - 在
MyLinkedList中的链表初始化构造函数中，我们给虚拟头节点分配内存空间_dummyHead = new LinkedNode(0)。 - 在
MyLinkedList链表类里的private部分，我们定义了链表的长度int _size，创建了虚拟头节点的指针LinkedNode* _dummyHead。 - 在
LinkedNode中的节点初始化构造函数中，我们给其中的值用参数赋值，在将next指针指向nullptr空指针。
反转链表
LeetCode206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表头节点。
双指针法
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->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);}};
- 需要特别注意的是，在
reverse递归函数中，每一条执行路径都必须要有return值，比如最后的return reverse(cur,temp)，尽管你知道了最后肯定是进入if判断返回头节点，也不可以省略return写成直接调用函数的形式，否则编译器在编译过程中就会检测到并报错。
递归法（逆向）
class Solution {
public:ListNode* reverseList(ListNode* head) {// 边缘条件判断if(head == NULL) return NULL;if (head->next == NULL) return head;// 递归调用，翻转第二个节点开始往后的链表ListNode *last = reverseList(head->next);// 翻转头节点与第二个节点的指向head->next->next = head;// 此时的 head 节点为尾节点，next 需要指向 NULLhead->next = NULL;return last;}
};
- 理解这个真的是花了我好大的功夫！还是要多接触多写才行，比较抽象。
- 递归主要就是“递”和”归“，”递“的过程是一步步深入找到临界点执行某基础操作，”归“则是不断
return回到调用前的函数执行某循环操作。 - 比如这道题目中，先在函数内不断调用函数，一次次将
head的next赋值给head，通过边缘条件找到最深处的head，这个就是最后一个节点也是我们需要输出答案的头节点，然后回到上一层将头节点用*last指针保存下来（ListNode *last = reverseList(head->next);最后一层给这一层返回了一个头节点），因为我们在”归“的过程中无法再用head调用到这个头节点了。 - 从现在开始，每一层都在反转
head与head->next，并让head指向空指针，然后用return last把最后需要返回的头节点代代相传下来。 - 最后我们就得到了一个反转的链表和其头节点的指针。
关于这个逆向递归方法的思考方式
我们没有那么大精力去思考完整个递归过程，于是以下的思考方式可以参考
- 首先我们这个函数的作用是传入一个头节点并返回反转后的链表的头节点
- 那么我们可以当作我们的函数已经实现了这个功能，于是我们拿来调用，得到了从第二个节点开始往后的反转链表的头节点
- 然后我们再反转当前的头节点（注意头节点
head的值从未改变过，只是每次调用时的头节点都是上一次调用的头节点的next节点）与第二个节点，返回调用函数获取到的反转链表头节点即可。 - 因为函数调用最终是要获取到头节点的，所以需要在前面增加一个边缘条件判断。
NULL和nullptr的区别
在 C++ 中，当 NULL 用于指针场景时，它会被隐式转换为「空指针」；但它的本质是整数 0，不是专门为指针设计的空值。
nullptr 是 C++11 标准新增的关键字，它的本质是「专门用于表示空指针的常量」，不属于整数类型，也不能隐式转换为整数类型，只能用于「指针相关场景」。
在调用重载函数的时候，NULL可能会出现BUG：
#include <iostream>
using namespace std;// 重载函数1：参数为 int 类型
void func(int x) {cout << "调用了 int 参数的函数，x = " << x << endl;
}// 重载函数2：参数为 指针类型
void func(char* p) {cout << "调用了 指针参数的函数，p 是空指针" << endl;
}int main() {// 1. 传入 NULL：本质是 0，优先匹配 int 参数的函数（不符合预期）func(NULL); // 输出：调用了 int 参数的函数，x = 0// 2. 传入 nullptr：专门的空指针，优先匹配 指针参数的函数（符合预期）func(nullptr); // 输出：调用了 指针参数的函数，p 是空指针return 0;
}
我们传入 NULL 的初衷是想调用「指针参数」的函数，但由于 NULL 是整数 0，编译器会优先匹配 int 参数的函数，这就违背了我们的初衷，而 nullptr 则能准确匹配指针参数的函数，避免这种隐蔽的 bug。