当前位置： 首页 > news >正文

暑期算法训练.11

news 2025/8/2 9:13:53

目录

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;
}

问题：

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

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

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

  2. n 被修改后不影响逻辑，但 k 被修改会导致后续组的反转次数错误。

这个是正确的：
for(int i=0; i<n; i++)  // 不修改n
{ListNode* tmp = cur1;for(int j=0; j<k; j++)  // 不修改k{// 反转逻辑}prev = tmp;
}

改进点：

  1. 使用 for 循环代替 while 循环：

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

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

  2. 避免了 k 被错误修改：

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

 

51.4 总结反思

今天的知识基本都用到了我在开篇所讲的那些知识

本篇完................. 

 

 

 

 

 

 

http://www.lryc.cn/news/605709.html

相关文章：

  • wpf之ControlTemplate
  • RabbitMQ 消费者确认 (Ack/Nack) （With Spring Boot）
  • HUD抬头显示器-杂散光测试设备 太阳光模拟器
  • FastGPT + Kymo AI生态创新平台，搭建企业智能化知识管理
  • TTS语音合成|GPT-SoVITS语音合成服务器部署，实现http访问
  • 自动驾驶控制算法——PID算法
  • Linux进程创建，终止与等待
  • 运作管理学习笔记1-运作管理基础
  • Docker 初学者需要了解的几个知识点 (五）：建容器需要进一步了解的概念
  • 蓝牙 BR/EDR 与 BLE PHY
  • c# net6.0+ 安装中文智能提示
  • JSX语法
  • LPC2132GPIO
  • elk部署加日志收集
  • mac环境配置rust
  • CentOS 7 上使用 Docker 安装 Jenkins 完整教程
  • 【数据结构初阶】--二叉树选择题专辑
  • 佳维视工业显示器在除尘与过滤设备中的应用
  • 操作系统系统面试常问(内存、快表、相关知识)
  • 关于npm前端项目编译时栈溢出 Maximum call stack size exceeded的处理方案
  • 专业鼠标点击器，自定义间隔次数
  • NPM打包时，报reason: getaddrinfo ENOTFOUND registry.nlark.com
  • 从Excel到工时管理系统：企业如何选择更高效的工时记录工具？
  • Verilog实现RPC从机(配合AXI_Slave使用)
  • 金融专题｜某跨境支付机构：以榫卯企业云平台 VPC 功能保障业务主体安全
  • 查询目前服务器所占的带宽的命令（上传和下载）
  • TTS语音合成|f5-tts语音合成服务器部署，实现http访问
  • 【Kiro Code 从入门到精通】重要的功能
  • 安全月报 | 傲盾DDoS攻击防御2025年7月简报
  • python中高效构建提示词