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

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 -- 链表(中)

不要觉得力扣核心代码模式麻烦&#xff0c;它确实比不上ACM模式舒服&#xff0c;可以自己处理输入输出 只是你对 链表 和 return 的理解不到位 &#x1f442; ▶ 屿前世 (163.com) &#x1f442; ▶ see you tomorrow (163.com) 目录 &#x1f382;两数相加 &#x1f6a9;删…...

数据结构面试常见问题

数据结构是计算机科学中非常重要的一部分&#xff0c;也是面试中经常被考察的内容。以下是一些在数据结构面试中常见的问题&#xff1a; 1. 数组 (Array): 描述数组和链表的区别。如何在数组中实现循环队列&#xff1f;给定一个数组&#xff0c;如何找到两个数的和等于给定值…...

蓝桥杯2024年第十五届省赛真题-R 格式(高精度乘法 + 加法)

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

普通人做抖音小店真的能赚钱吗?可以,但更取决于个人

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

基于单链表实现通讯管理系统!(有完整源码!)

​ 个人主页&#xff1a;秋风起&#xff0c;再归来~ 文章专栏&#xff1a;C语言实战项目 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 1、前言 友友们&#xff0c;这篇文章是基于单链…...

MATLAB入门介绍

MATLAB是由MathWorks公司开发的一款专业的数学计算软件&#xff0c;主要用于算法开发、数据可视化、数据分析以及数值计算等领域。它提供了一个易于使用的环境&#xff0c;让用户可以通过矩阵计算、函数和数据绘图、用户界面的创建以及编程和文档编写来解决各种数学问题。 MATL…...

【k8s】:深入理解 Kubernetes 中的污点(Taints)与容忍度(Tolerations)

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

Angular 使用DomSanitizer防范跨站脚本攻击

跨站脚本Cross-site scripting 简称XSS&#xff0c;是代码注入的一种&#xff0c;是一种网站应用程序的安全漏洞攻击。它允许恶意用户将代码注入到网页上&#xff0c;其他用户在使用网页时就会收到影响&#xff0c;这类攻击通常包含了HTML和用户端脚本语言&#xff08;JS&…...

(八)PostgreSQL的数据库管理

PostgreSQL的数据库管理 基础信息 OS版本&#xff1a;Red Hat Enterprise Linux Server release 7.9 (Maipo) DB版本&#xff1a;16.2 pg软件目录&#xff1a;/home/pg16/soft pg数据目录&#xff1a;/home/pg16/data 端口&#xff1a;57771 创建数据库 CREATE DATABASE创建一…...

外包干了30天,技术倒退明显

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

ruoyi-nbcio-plus基于vue3的flowable的自定义业务单表例子的升级修改

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a…...

【ENSP】华为三层交换机配置AAA认证,开启telnet服务

配置步骤 1.给交换机配置ip地址&#xff0c;以便登陆 2.配置AAA&#xff0c;用户名&#xff0c;密码&#xff0c;服务类型&#xff0c;用户权限 3.配置接入设备的数量 4.开启telnet服务 LSW2交换机配置 u t m #关闭提示 sys …...

collections模块下的Counter函数讲解

&#x1f4da;博客主页&#xff1a;knighthood2001 ✨公众号&#xff1a;认知up吧 &#xff08;目前正在带领大家一起提升认知&#xff0c;感兴趣可以来围观一下&#xff09; &#x1f383;知识星球&#xff1a;【认知up吧|成长|副业】介绍 ❤️感谢大家点赞&#x1f44d;&…...

HarmonyOS开发实例:【分布式邮件】

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

llama2.c与chinese-baby-llama2语言模型本地部署推理

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

008、Python+fastapi,第一个后台管理项目走向第8步:ubutun 20.04下安装vscode+python环境配置

一、说明 白飘了3个月无影云电脑&#xff0c;开始选了个windows server 非常不好用&#xff0c;后台改为ubuntu想升级到22&#xff0c;没成功&#xff0c;那就20.04吧。 今天先安装下开发环境&#xff0c;后续2个月就想把他当做开发服务器&#xff0c;不知道行不行&#xff0c;…...

2024.4.16 驱动开发

思维导图...

如何在 Ubuntu 14.04 上更改 PHP 设置

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

【光伏企业】光伏项目怎么做才能提高效率?

一、精细化项目管理 项目规划&#xff1a;在项目启动前&#xff0c;进行充分的调研和规划&#xff0c;明确项目的目标、规模、预算和时间表&#xff0c;确保各项资源得到合理分配。 团队建设&#xff1a;组建一支高效、专业的项目团队&#xff0c;确保团队成员具备光伏领域的…...

毕设选51还是stm32?51太简单?

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

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 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 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看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...