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可能更适合。我这里有一套嵌入式入门教程,不仅包含了详细的视频讲解,项目实战。如果你渴望学习嵌入式,不妨点个关注ÿ…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...