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可能更适合。我这里有一套嵌入式入门教程,不仅包含了详细的视频讲解,项目实战。如果你渴望学习嵌入式,不妨点个关注ÿ…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...

WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...

Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...

高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...