链表基础知识回顾+算法题打卡
链表的概念以及结构
概念：链表是一种物理存储结构上不连续的，非顺序的存储结构，数据元素的顺序是通过节点中的指针来实现的。
结构：（此处指单向非循环链表）链表中每个节点的存储元素一般包含两部分，数据和下一个节点的地址。
struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };
遍历打印链表
在链表中访问元素需要通过每个节点中存放的下一个元素地址，才能找到下一个节点的位置，具体代码实现如下：
//遍历链表 void SListPrint(SListNode* phead) { SList* cur = phead; //这里我们创建一个指针来指向头结点的位置 while(cur) { print("%d->", cur->date); //打印当前节点的数据 cur = cur->next; //将指针指向下一个节点 } }
申请节点
链表中每一个节点都是动态开辟出来的，所以要新增一个节点之前要先申请一个节点，每个节点的大小为该结构体的大小，开辟成功之后，该节点数据部分存放输入的值，地址（next）置为NULL。
C语言代码展示如下（这部分主要是为了了解具体实现步骤）：
//申请节点 SListNode* SListBuyBode(SListDataType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SlistNode)); //申请地址空间 if (newnode == NULL) //判断是否成功 { perror("nalloc:"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
用C++则更为简洁且更加安全，代码如下：
struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* newNode = new ListNode(newValue);
尾插
因为链表无法通过元素下标访问，所以我们要想知道下一个节点的位置，只能通过遍历整个链表。
这里分为两种情况：
- 链表为空，直接插入
- 链表不为空，遍历找到尾节点，再插入
//尾插 void SListPushBack(SListNode** head, int x) { ListNode* newNode = new ListNode(x); //创建一个新节点 if(head == nullptr) { *head = newNode; //如果要插入的链表为为空，则直接将新建的节点作为头节点即可 } else { ListNode* current = head; while(current -> != nullptr) { current = current -> next; } current->next = newNode; } }
头插
在头部插入的话，只需要将当前节点置为头节点，再将当前节点的next改为头节点。
//头插 void SListPushFront(SListNode** head, int x) { //申请新增节点 SListNode* newNode = new SListNode(x); //将当前节点的next改为头节点 newNode->next = *head; //将头节点设为当前节点 *head = newNode; }
函数参数 SListNode* head 是值传递，这意味着函数内部对 head 的修改不会影响到函数外部的实参。如果要修改外部的头指针，应该传递头指针的指针（SListNode** head）或者头指针的引用（SListNode*& head）
删除
- 链表为空，不能删除
- 删除头节点：如果要删除的是头节点，先保存头节点，再将下一个节点更新为头节点
- 删除其余位置节点
具体代码展示如下：
//删除链表中值为 target的节点 ListNode* deleteNode(ListNode* head, int target) { //链表为空 if(head == nullptr) { return nullptr; } //删除头节点 if(head->data == target) { //先记下头节点位置 ListNode* temp = head; head = head -> next; delete temp; return head; } //删除其余位置 ListNode* cur = head; //找到目标位置的前一个节点 while(cur->next->data != target && cur->next != nullptr) { cur = cur - next; } if(cur->next != nullptr) { ListNode* temp = cur->next; //记录下要删除节点的下一个节点 cur->next = cur->next->next;//跳过要删除的节点 delete temp;//删除节点 } return head; }
最后再加一个判断if(cur->next !=nullptr)的原因：
目标节点不存在于链表中：如果链表中不存在值为 target 的节点，while 循环会一直执行到链表末尾，此时 current->next 为 nullptr。当 while 循环条件 current->next != nullptr && current->next->val != target 中的 current->next == nullptr 时，循环终止。在这种情况下，就不应该执行删除操作，因为没有找到要删除的节点。所以 if (current->next != nullptr) 这个判断可以防止在链表中没有目标节点时误删节点或引发空指针异常。
null和nullptr的区别
在 C++ 中，nullptr 和 NULL 都用于表示空指针，但它们之间存在一些重要区别：
nullptr：nullptr是 C++ 11 引入的关键字，它的类型是std::nullptr_t。这是一种特殊的类型，专门用于表示空指针。它可以隐式转换为任何指针类型，使得代码在处理空指针时更加类型安全。例如：
int* ptr1 = nullptr; double* ptr2 = nullptr;
NULL：NULL是一个宏，通常在 C 标准库头文件（如<stdio.h>）或 C++ 兼容头文件中定义。在 C 语言中，它通常被定义为((void*)0)，在 C++ 中，它通常被定义为0或0L（长整型 0）。由于它本质上是整数类型（在 C++ 中），当将NULL赋值给指针时，可能会导致一些潜在的类型混淆问题。例如，假设有一个函数重载，同时接受指针和整数类型参数：
void func(int num); void func(int* ptr); func(NULL); // 在C++ 中，这可能会导致编译错误或调用错误的函数，因为NULL可能被解释为整数0 func(nullptr); // 明确调用func(int* ptr)
牛客练习题
BM1 反转链表
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* ReverseList(ListNode* head) { // write code here ListNode* per = nullptr; //定义前序节点 while(head) //判断是否到结尾 { ListNode* temp = head ->next; //记录下一个节点 head ->next = per; //反转当前节点 per = head; //前序节点向后移 head = temp; //当前节点后移 } return per; } };
总结：就是逐个翻转，定义了前序节点和当前节点，逐步翻转，逐步后移，直到链表尾部。
BM2 链表内指定区间反转
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { // write code here //定义一个表头 ListNode* res = new ListNode(-1); res -> next = head; //定义前序节点 ListNode* per = res; //定义当前节点 ListNode* cur = head; //找到m位置 for(int i = 1; i < m; i++) { per = cur; cur = cur->next; } //从m反转到n for(int i = m; i < n; i++) { ListNode* temp = cur->next;//记录当前节点下一个节点 cur->next= temp->next;//越过当前节点 temp->next = per->next;//当前节点反转 per->next = temp;//前序节点连到最后 } //返回去掉表头 return res->next; } };
理解起来是比较抽象，我也是看了半天才懂，反正多写两遍就记住了，下面有张当时理解的手绘图（明天补上）ok已补上
BM3 链表中的节点每k个一组翻转
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* reverseKGroup(ListNode* head, int k) { // write code here //找到每次反转的尾部 ListNode* tail = head; //遍历k次找到当前组的尾部 for(int i = 0; i < k; i++) { if(tail == nullptr) return head; tail = tail->next; } //定义所需的前序节点和当前节点 ListNode* per = nullptr; ListNode* cur = head; while(cur != tail) { ListNode* temp = cur->next; cur->next = per; per = cur; cur = temp; } head->next=reverseKGroup(tail, k); return per; } };
总结：
- 定义一个尾部，遍历k找到当前组的队尾（如果遍历时剩下的不足k个，则直接返回最后一组的head）
- 定义前序，当前节点，对当前小组进行翻转
- 记下当前组的head（翻转前为头，现在是尾），给head赋值为递归函数的返回值（即下一组的头节点），递归传入当前tail(指向当前组的下一个位置，即下一组的头部)
- 返回当前的首部
理解了也不难，总之还是要多写两遍
BM4 合并两个排序的链表
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { // write code here ListNode* res = new ListNode(-1); //定义一个表头 ListNode* tail = res; //用来遍历的指针 while(pHead1 != nullptr && pHead2 != nullptr) { if(pHead1->val < pHead2->val) { tail->next = pHead1; pHead1 = pHead1->next; } else { tail->next = pHead2; pHead2 = pHead2->next; } tail = tail->next; } //处理剩余的 if(pHead1 != nullptr) { tail->next = pHead1; } else { tail->next = pHead2; } return res->next; } };
这个没什么好说的了，看一下应该都能懂
BM5 合并k个已排序的链表
主要是递归和分治的一个思想，将链表数组不断等分，直到只剩最后两个数组，然后将这两个数组排序合并，在逐步回归合并
主要难点就是递归合并，排序部分跟上一道题一模一样
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param lists ListNode类vector * @return ListNode类 */ //用来合并两个链表 ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { // write code here ListNode* res = new ListNode(-1); //定义一个表头 ListNode* tail = res; //用来遍历的指针 while(pHead1 != nullptr && pHead2 != nullptr) { if(pHead1->val < pHead2->val) { tail->next = pHead1; pHead1 = pHead1->next; } else { tail->next = pHead2; pHead2 = pHead2->next; } tail = tail->next; } if(pHead1 != nullptr) { tail->next = pHead1; } else { tail->next = pHead2; } return res->next; } //划分合并区间 ListNode* divideMerge(vector<ListNode*> &lists, int left, int right) { if(left > right) return NULL; else if(left == right) //正好剩下最后一个链表 { return lists[left]; } //从中间分成两段 int mid = (left + right)/2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right)); } ListNode* mergeKLists(vector<ListNode*>& lists) { // write code here //k个列表归并排序 return divideMerge(lists, 0, lists.size() - 1); } };
能看懂，但是自己完整写下来还是有困难，先这样吧，后面写多了应该会好点。
好的今天就到这里！！！
