hot100 -- 链表(中)
不要觉得力扣核心代码模式麻烦,它确实比不上ACM模式舒服,可以自己处理输入输出
只是你对 链表 和 return 的理解不到位
👂 ▶ 屿前世 (163.com)
👂 ▶ see you tomorrow (163.com)
目录
🎂两数相加
🚩删除链表倒数第 N 个节点
AC 双指针
AC 栈
AC 计算链表长度
🌼两两交换链表中的节点
AC 递归
AC 迭代
🌼K 个一组翻转链表
🎂两数相加
2. 两数相加 - 力扣(LeetCode)
1)l1, l2 长度可能不一样,假设短的后面全是 0,通过三目运算符得到 当前节点的值,比如
n1 = l1 ? l1->val : 0
2)sum = n1 + n2 + 进位,%10 当前位,/10 进位
3)注意给节点赋值方式
tail->next = new ListNode(...);
4)可能漏最后一次进位,while() 结束后还要来一次
时间 O(max(m, n)),空间 O(1)
/*** Definition for singly-linked list.* 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 *head = nullptr, *tail = nullptr;int temp = 0; // 进位while (l1 || l2) {int n1 = l1 ? l1->val : 0; // l1 的值int n2 = l2 ? l2->val : 0;int sum = n1 + n2 + temp;if (!head) // 第1次head = tail = new ListNode(sum % 10); // 注意赋值方式else {// tail 上一步已经初始化, 所以现在是 tail->nexttail->next = new ListNode(sum % 10); // 先给下一赋值tail = tail->next; // 再移动}temp = sum / 10; // 进位// l1, l2 向后移动if (l1) l1 = l1->next;if (l2) l2 = l2->next;}// 最后一次进位if (temp) tail->next = new ListNode(temp);return head; // 不返回 tail, 防止 nullptr}
};
🚩删除链表倒数第 N 个节点
19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)
注意:链表的题,如果出现 Node->next,那么这个 Node 一定不为 nullptr,否则会报错
1,双指针:一前一后,前面的先移动 n 个位置,然后开始同步移动
2,栈:思路类似双指针,最终都是遍历到待删除节点前一个(从栈顶开始出栈)
3,链表长度:思路类似前面,借助哑节点,避免对删除头节点的处理,遍历两次即可
AC 双指针
时间 O(L),空间 O(1),L 链表长度
自己写的
/*** Definition for singly-linked list.* 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* removeNthFromEnd(ListNode* head, int n) {ListNode *fast = head, *slow = head;// 前后指针 -- 找到倒数第 n 个节点, 即 slowwhile (n--)fast = fast->next;// 删除头节点if (!fast) {ListNode *temp = head;head = temp->next;delete temp;return head;}while (fast->next)slow = slow->next, fast = fast->next;// 删除 slow 下一节点ListNode *bad = slow->next; // 要删除的节点slow->next = slow->next->next;bad->next = nullptr;delete bad;// 上面处理了头节点被删除的情况,所以这里可以 return headreturn head; }
};
官解重写
删除倒数第 n 个节点,通过指针的 next 来操作,最后的 delete 只是为了手动释放堆区数据(自己new的自己delete)
bad 的作用是,防止删的是第一个元素,因为最终会遍历到删除节点的前一个
如果不用 bad,就像前面的代码一样,特殊处理删除节点是头节点的情况
/*** Definition for singly-linked list.* 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* removeNthFromEnd(ListNode* head, int n) {// 初始化 head 上一位置, bad->next = headListNode *bad = new ListNode(0, head); ListNode *fast = head, *slow = bad; // slow 初始化为 badwhile (n--)fast = fast->next;while (fast) {fast = fast->next;slow = slow->next;}// 此时 slow 位于删除节点 上一位置slow->next = slow->next->next; // 更新连接ListNode *ans = bad->next; // 新的头节点delete bad;return ans; // 返回新的头节点}
};
AC 栈
/*** Definition for singly-linked list.* 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* removeNthFromEnd(ListNode* head, int n) {stack<ListNode *> s;// temp 的作用是,防止删的是第一个元素,因为最终会遍历到删除节点的前一个ListNode *temp = new ListNode(0, head);ListNode *cur = temp;// 链表节点全部入栈while (cur) {s.push(cur); // push_back 是 vectorcur = cur->next;}// 弹出 n 个元素后,栈顶就是待删除节点前一个while (n--) s.pop();ListNode *prev = s.top(); prev->next = prev->next->next; // 先重新连接ListNode *ans = temp->next; // 再赋值新的头节点delete temp;return ans;}
};
AC 计算链表长度
同样,类似上面两种,通过头节点前的,哑节点,避免对删除头节点这种情况的处理
/*** Definition for singly-linked list.* 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* removeNthFromEnd(ListNode* head, int n) {ListNode *temp = new ListNode(0, head); // 哑节点,避免对头节点删除的处理ListNode *cur = temp;int len = 0;// 链表长度while (cur->next) { // 长度容易错len++;cur = cur->next;}cur = temp;int count = len - n;// 哑节点移动 len - n + 1,即待删除节点// 所以,移动 len - n,刚好待删除前一个while (count--) cur = cur->next;cur->next = cur->next->next;ListNode *ans = temp->next; // 新的头节点delete temp;return ans;}
};
🌼两两交换链表中的节点
24. 两两交换链表中的节点 - 力扣(LeetCode)
AC 递归
head之前的不用处理,举个例子,比如
转换后 head = swapPairs(temp->next),把两两视作一个整体,那么两两中的后一个,指向哪里,取决于后面递归的结果,所以只需考虑当前层
时间 O(n),空间 O(n)(递归栈深度 n)
/*** Definition for singly-linked list.* 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:// head 表示递归时,当前两两交换节点的前一个ListNode* swapPairs(ListNode* head) {// 递归出口if (head == nullptr || head->next == nullptr)return head; // 只剩0个 或 1个节点// 只看当前层:交换两个节点ListNode *temp = head->next; head->next = swapPairs(temp->next); // 递归交换剩余节点temp->next = head;return temp; // 返回新的头节点}
};
AC 迭代
类似冒泡排序,直接交换,但是需要借助哑节点 temp,比如
temp->Node1->Node2
👇
temp->Node2->Node1
时间 O(n),空间 O(1)
/*** Definition for singly-linked list.* 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* swapPairs(ListNode* head) {ListNode *temp = new ListNode(0, head); // 初始 temp->next == headListNode *tempHead = temp; // 头节点前一个// 递归中的 head 是当前节点// 迭代中的 head 只表示原链表头节点// 所以 while 中不能用 head, 应该用 tempwhile (temp->next != nullptr && temp->next->next != nullptr) {ListNode *Node1 = temp->next;ListNode *Node2 = temp->next->next;// temp->Node1->Node2 ----> temp->Node2->Node1temp->next = Node2;Node1->next = Node2->next;Node2->next = Node1;// 新的哑节点temp = Node1;}ListNode *ans = tempHead->next; // 新链表头节点// delete tempHead; // 删除哑节点return ans; // 新的头节点}
};
🌼K 个一组翻转链表
25. K 个一组翻转链表 - 力扣(LeetCode)
模拟:迭代反转 + 新建连接
以下是新建连接的 3 个步骤
k = 3 也一样
和上/下一组新建连接时,要从外层开始,就是p0->next->next到p0->next最后才是p0
p0->next->next = cur; // 下一组头 p0->next = nex; // 上一组尾 p0 = p1; // 更新p0
时间 O(n),空间 O(1)
/*** Definition for singly-linked list.* 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* reverseKGroup(ListNode* head, int k) {// 链表长度 lenint len = 0;for (ListNode *cur = head; cur; cur = cur->next)len++;// temp->next == head(temp/p0 -- 哑节点/哨兵节点)ListNode *temp = new ListNode(0, head);ListNode *p0 = temp; // p0 k个一组第一个节点的前一个ListNode *nex = nullptr, *cur = head;// k 个一组反转for (; len >= k; len -= k) {// 迭代 -- 反转(参考反转链表I)// 因为哨兵节点的存在,所以是 k 次而不是 k-1 次反转for (int i = 0; i < k; ++i) { // k 次反转ListNode *pre = cur->next; // pre 右移cur->next = nex; // 反转nex = cur; // nex 右移cur = pre; // cur 右移}// 当前组 与 上一组尾&&下一组头 连接ListNode *p1 = p0->next; // 新的p0p0->next->next = cur; // 下一组头p0->next = nex; // 上一组尾p0 = p1; // 更新p0}return temp->next; // 返回新链表的头节点}
};
相关文章:

hot100 -- 链表(中)
不要觉得力扣核心代码模式麻烦,它确实比不上ACM模式舒服,可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 👂 ▶ 屿前世 (163.com) 👂 ▶ see you tomorrow (163.com) 目录 🎂两数相加 🚩删…...
数据结构面试常见问题
数据结构是计算机科学中非常重要的一部分,也是面试中经常被考察的内容。以下是一些在数据结构面试中常见的问题: 1. 数组 (Array): 描述数组和链表的区别。如何在数组中实现循环队列?给定一个数组,如何找到两个数的和等于给定值…...

蓝桥杯2024年第十五届省赛真题-R 格式(高精度乘法 + 加法)
本题链接:蓝桥杯2024年第十五届省赛真题-R 格式 - C语言网 题目: 样例: 输入 2 3.14 输出 13 思路: 根据题意,结合数据范围,这是一道模板的高精度乘以低精度问题。 题意是double 类型 d 与…...

普通人做抖音小店真的能赚钱吗?可以,但更取决于个人
大家好,我是电商花花。 现在做抖音小店的基本上都是一些新商家,对于我们众多零基础的朋友来说,是期待也是一份挑战。 抖音小店作为一个充满机会的新兴平台,许多人都欣喜的投入其中,期望能够借此来改变自己的命运&…...

基于单链表实现通讯管理系统!(有完整源码!)
个人主页:秋风起,再归来~ 文章专栏:C语言实战项目 个人格言:悟已往之不谏,知来者犹可追 克心守己,律己则安! 1、前言 友友们,这篇文章是基于单链…...
MATLAB入门介绍
MATLAB是由MathWorks公司开发的一款专业的数学计算软件,主要用于算法开发、数据可视化、数据分析以及数值计算等领域。它提供了一个易于使用的环境,让用户可以通过矩阵计算、函数和数据绘图、用户界面的创建以及编程和文档编写来解决各种数学问题。 MATL…...

【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations)
【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations) 1、污点(Taints)2、容忍度(Tolerations)3、示例演示-测试污点的具体应用场景3.1 给节点打污点&…...

Angular 使用DomSanitizer防范跨站脚本攻击
跨站脚本Cross-site scripting 简称XSS,是代码注入的一种,是一种网站应用程序的安全漏洞攻击。它允许恶意用户将代码注入到网页上,其他用户在使用网页时就会收到影响,这类攻击通常包含了HTML和用户端脚本语言(JS&…...
(八)PostgreSQL的数据库管理
PostgreSQL的数据库管理 基础信息 OS版本:Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本:16.2 pg软件目录:/home/pg16/soft pg数据目录:/home/pg16/data 端口:57771 创建数据库 CREATE DATABASE创建一…...

外包干了30天,技术倒退明显
先说情况,大专毕业,18年通过校招进入湖南某软件公司,干了接近6年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能…...

ruoyi-nbcio-plus基于vue3的flowable的自定义业务单表例子的升级修改
更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码: https://gitee.com/nbacheng/ruoyi-nbcio 演示地址:RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码:…...

【ENSP】华为三层交换机配置AAA认证,开启telnet服务
配置步骤 1.给交换机配置ip地址,以便登陆 2.配置AAA,用户名,密码,服务类型,用户权限 3.配置接入设备的数量 4.开启telnet服务 LSW2交换机配置 u t m #关闭提示 sys …...
collections模块下的Counter函数讲解
📚博客主页:knighthood2001 ✨公众号:认知up吧 (目前正在带领大家一起提升认知,感兴趣可以来围观一下) 🎃知识星球:【认知up吧|成长|副业】介绍 ❤️感谢大家点赞👍&…...

HarmonyOS开发实例:【分布式邮件】
概述 基于TS扩展的声明式开发范式编程语言编写的一个分布式邮件系统,可以由一台设备拉起另一台设备,每次改动邮件内容,都会同步更新两台设备的信息。效果图如下: 搭建OpenHarmony开发环境 完成本篇Codelab我们首先要完成开发环境…...

llama2.c与chinese-baby-llama2语言模型本地部署推理
文章目录 简介Github文档克隆源码英文模型编译运行中文模型(280M)main函数 简介 llama2.c是一个极简的Llama 2 LLM全栈工具,使用一个简单的 700 行 C 文件 ( run.c ) 对其进行推理。llama2.c涉及LLM微调、模型构建、推理端末部署(…...

008、Python+fastapi,第一个后台管理项目走向第8步:ubutun 20.04下安装vscode+python环境配置
一、说明 白飘了3个月无影云电脑,开始选了个windows server 非常不好用,后台改为ubuntu想升级到22,没成功,那就20.04吧。 今天先安装下开发环境,后续2个月就想把他当做开发服务器,不知道行不行,…...

2024.4.16 驱动开发
思维导图...
如何在 Ubuntu 14.04 上更改 PHP 设置
简介 PHP 是一种服务器端脚本语言,被许多流行的 CMS 和博客平台如 WordPress 和 Drupal 所使用。它也是流行的 LAMP 和 LEMP 堆栈的一部分。更新 PHP 配置设置是设置基于 PHP 的网站时的常见任务。定位确切的 PHP 配置文件可能并不容易。通常在服务器上会有多个 PH…...

【光伏企业】光伏项目怎么做才能提高效率?
一、精细化项目管理 项目规划:在项目启动前,进行充分的调研和规划,明确项目的目标、规模、预算和时间表,确保各项资源得到合理分配。 团队建设:组建一支高效、专业的项目团队,确保团队成员具备光伏领域的…...

毕设选51还是stm32?51太简单?
如果你更倾向于挑战和深入学习,STM32可能是更好的选择。如果你希望更专注于底层硬件原理,51可能更适合。我这里有一套嵌入式入门教程,不仅包含了详细的视频讲解,项目实战。如果你渴望学习嵌入式,不妨点个关注ÿ…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...

给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...