47. 力扣203 移除链表元素

47.1 题目解析：

编辑

47.2 算法思路：

47.3 代码演示：

编辑

48. 力扣2.两数相加

48.1 题目解析：

编辑

48.2 算法思路;

48.3 代码演示：

48.4 总结反思：

49. 力扣24 两两交换链表中的节点

49.1 题目解析：

49.2 算法思路：

49.3 代码演示：

编辑

49.4 总结反思

50. 力扣 143 重排链表

50.1 题目解析：

50.2 算法思路：

50.3 代码演示：

编辑

50.4 总结反思

51 力扣 25 k个1组翻转链表

51.1题目解析：

51.2 算法思路：

编辑

51.3 代码演示：

编辑

51.4 总结反思

今天咱们讲链表，以及链表常用操作总结：

就是咱们接下来的题目，基本上都会用到这几种方法：

1.画图！！！（这个画图特别重要），因为画图直观加形象加便于我们理解

2.咱们在做题的时候，可以引入虚拟节点：

【1】虚拟头结点可以简化边界的处理。

【2】可以统一操作，不需要再单独的对头节点进行特殊操作。为什么这么说呢？是因为

那么接下来咱们通过一道题目来进行实际的探查：

47. 力扣203 移除链表元素

47.1 题目解析：

题目很简单。就是删除值为val的某个节点

47.2 算法思路：

就是遍历整个链表，找到值为val的那个元素，然后再跳过这个元素即可。

47.3 代码演示：

//不带虚拟头结点
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;}
};

这个是不带虚拟头结点的版本，可以看出来，咱们需要单独的处理一下头结点，然后再是处理其他的节点。并且，如果这样的话，步骤就比较繁琐，而且不容易统一处理方式

//带虚拟头结点的版本
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy = new ListNode(0); // 虚拟头节点指向headdummy->next = head;ListNode* cur = dummy;while (cur->next != nullptr) {if (cur->next->val == val) {cur->next = cur->next->next; // 统一删除逻辑，直接跳过这个节点即可，也是单向链表通常的删除逻辑}else {cur = cur->next;}}return dummy->next; // 新头节点}
};

这个是带虚拟头结点的版本，是不是很爽，基本可以统一处理节点了（包括头节点）。

所以，虚拟头节点的好处就是：

1. 避免头节点的特殊处理

问题：在链表操作中，如果直接操作头节点（如删除、反转、插入等），通常需要额外判断：

如果删除头节点，需要重新指定 head。

如果插入新节点到头部，需要更新 head。

虚拟头结点的作用：

提供一个统一的“前驱节点”，使得头节点和其他节点的操作逻辑一致。

无论原头节点如何变化，dummy->next 始终指向新头节点。

2. 简化代码逻辑

没有虚拟头结点：需要单独处理头节点，代码分支增多。

有虚拟头结点：所有节点（包括原头节点）都有前驱节点，可以用统一逻辑处理。

在C++中，虚拟头节点一般这样创建：

ListNode* dummy = new ListNode(0); // 值任意，一般用0
dummy->next = head; // 指向原头节点
// ... 操作链表
return dummy->next; // 返回新头节点

3.不要吝啬空间，该创建的时候就得创建，这样可以省去不少的麻烦：

想必大家多多少少都做过这种题目吧，就是断开两个节点之间的链接，让第三个节点链接上去。那么此时，咱们如果不定义一个next节点变量，直接就有两个变量（prev，cur）去连接的话，此时就得注意一下顺序了。只能按照咱们图中所指的顺序来进行链接。

prev->next->prev=cur;
cur->next=prev->next;
prev->next=cur;
cur->prev=prev;

如果前两行与后两行颠倒了，先执行后两行，那么这样的话，会发现找不到后面那个节点了，也会导致cur->next=cur，自己指向自己，死循环。所以，这个时候就体现了，再定义一个新变量的必要性。再定义一个新变量，就不需要再担心执行的顺序了，管你先执行那个，都可以。

4.快慢指针

一般用于链表中环的判断，找到链表中环的入口，找到链表中倒数第n个节点。

而咱们链表的常用操作就是1.创建一个新的节点，2.尾插 3.头插（这个头插法在逆序链表中还是比较常用的）

这个是尾插，还是比较简单的。

这个是头插。相对于尾插来说，还是复杂一点的。

48. 力扣2.两数相加

48.1 题目解析：

这个题目有个关键的地方就是逆序操作，咱们可以直接从头开始加（因为这个是逆序存储的），即2,4,3 逆序存储为 3,4,2。5，6，4 逆序存储为4,6,5 。那么3，4，2与4，6，5相加，由于是从最低位开始加，那么逆序之后，对应的就从链表的头开始相加，非常的方便。

48.2 算法思路;

直接模拟两数相加即可

以上就是这个题目的所有的算法思路。

48.3 代码演示：

struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* next) : val(x), next(next) {}};
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1; ListNode* cur2 = l2;ListNode* newnode = new ListNode(0);//创建一个虚拟头结点，记录最终结果int t = 0;ListNode* prev = newnode;while (cur1 || cur2 || t){if (cur1){t += cur1->val;cur1 = cur1->next;}if (cur2){t += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(t % 10);//新建一个节点才能去存储数字，因为此时newnode后面并没有节点。prev = prev->next;t /= 10;}ListNode* next = newnode->next;delete newnode;return next;}
};

48.4 总结反思：

这道题目充分的利用了上面的知识，所以还得具备充分的知识储备才可以。

49. 力扣24 两两交换链表中的节点

49.1 题目解析：

本题交换节点需要注意的是，不可以只交换节点里面的数值，必须得连着节点一起交换才可以。

49.2 算法思路：

OK，算法思路就是上面我写的这些，大家好好的参悟一下

49.3 代码演示：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;//若是链表为空，或者是链表只有一个元素，直接返回。注意，这里判断的标准时head，因为head才是真正的头结点，而不是newHead。判断这个的目的是为了预防下面的cur->next（cur为空，cur就是头结点，链表为空）与next->next（链表只有一个元素，此时next为空），空指针解引用ListNode* newHead = new ListNode(0);newHead->next = head;//head才是真正的头结点ListNode* prev = newHead;ListNode* cur = prev->next; ListNode* next = cur->next; ListNode* nnext = next->next;while (cur && next){//更新节点prev->next = next;next->next = cur;cur->next = nnext;//交换指针prev = cur;cur = nnext;if (cur) next = cur->next;if (next) nnext = next->next;}ListNode* kk = newHead->next;delete newHead;return kk;}
};

49.4 总结反思

其实这道题目也是用到了上面咱们所说的这些算法，大家还是得好好的参悟一下

50. 力扣 143 重排链表

50.1 题目解析：

这个题目其实是让你按照一定得顺序重新排一下链表

那么其实题目就是这样的，所以咱们可以分为三个步骤

1.找到链表的中间节点

使用快慢指针（一定要画图，考虑使用slow得落点在哪里）

2.把后面的部分逆序

使用双指针（或者三指针），或者头插法（推荐）完成逆序

3.合并两个有序链表，（双指针），按照一定得顺序合并

50.2 算法思路：

关于slow的落点，咱们直接砍掉slow后面的部分给逆序即可。不过需要引入虚拟头结点。一开始得先头插进第二个链表：

50.3 代码演示：

class Solution {
public:void reorderList(ListNode* head) {if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;//先找到中间节点ListNode* slow = head; ListNode* fast = head;while (fast && fast->next)//注意循环条件是这个，不是slow<fast{slow = slow->next;fast = fast->next->next;}//之后使用头插法对slow后面的部分进行逆序ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr;while (cur){ListNode* next = cur->next;//再定义一个变量存储这个cur，就是为了防止顺序问题cur->next = head2->next;head2->next = cur;cur = next;}//之后进行合并链表ListNode* kk = new ListNode(0);ListNode* prev = kk;ListNode* cur1 = head;ListNode* cur2 = head2->next;while (cur1){//先合并第一个链表prev->next = cur1;cur1 = cur1->next;prev = prev->next;//再合并第二个链表if (cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete kk;}
};

这样的代码量，放在整个链表对应的题目里面，算是比较多的了

50.4 总结反思

重点的东西还是开篇所讲的那些东西，还是希望大家要好好的研读，最好记住。

51 力扣 25 k个1组翻转链表

51.1题目解析：

其实这一题就考了一个模拟，并且也用到了逆序

51.2 算法思路：

51.3 代码演示：

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {//求出需要逆序多少组int n = 0;ListNode* cur = head;while (cur){cur = cur->next;n++;}n /= k;//重复n次，将长度为k的链表逆序即可ListNode* newHead = new ListNode(0);ListNode* prev = newHead;ListNode* cur1 = head;for (int i = 0; i < n; i++){ListNode* tmp = cur1;//把一开始的cur1的位置给存起来，由于是逆序存储，所以说后面的tmp的位置，就是下一组逆序头插的位置for (int j = 0; j < k; j++)//不可写成whilw(k--)/*k 被修改后没有恢复：内层 while (k--) 会直接修改 k 的值，导致后续循环（如果有）的 k 不正确。例如：第一次循环 k = 3，执行完 while (k--) 后 k = -1。如果还有第二次循环，k 已经变成 - 1，导致内层循环不执行，逻辑错误。n 被修改后不影响逻辑，但 k 被修改会导致后续组的反转次数错误。*/{ListNode* next = cur1->next;cur1->next = prev->next;prev->next = cur1;cur1 = next;}prev = tmp;}//剩下的直接接在后面即可prev->next = cur1;ListNode* cur2 = newHead->next;delete newHead;return cur2;}
};

这个地方，作者一开始写的时候，出现了一个失误，给大家看一下：

这个是错误的：
while(n--)  // 直接修改n的值
{ListNode* tmp = cur1;while(k--)  // 直接修改k的值{// 反转逻辑}prev = tmp;
}
问题：

k 被修改后没有恢复：内层 while(k--) 会直接修改 k 的值，导致后续循环（如果有）的 k 不正确。例如：

第一次循环 k=3，执行完 while(k--) 后 k=-1。

如果还有第二次循环，k 已经变成 -1，导致内层循环不执行，逻辑错误。

n 被修改后不影响逻辑，但 k 被修改会导致后续组的反转次数错误。
这个是正确的：
for(int i=0; i<n; i++)  // 不修改n
{ListNode* tmp = cur1;for(int j=0; j<k; j++)  // 不修改k{// 反转逻辑}prev = tmp;
}
改进点：

使用 for 循环代替 while 循环：

for(int j=0; j<k; j++) 不会修改 k 的值，确保每次反转都是 k 个节点。

for(int i=0; i<n; i++) 也不会修改 n，但即使修改 n 也不会影响逻辑。

避免了 k 被错误修改：

由于 k 保持不变，每次都能正确反转 k 个节点。