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

算法沉淀——链表(leetcode真题剖析)

在这里插入图片描述

算法沉淀——链表

  • 01.两数相加
  • 02.两两交换链表中的节点
  • 03.重排链表
  • 04.合并 K 个升序链表
  • 05.K个一组翻转链表

链表常用技巧

1、画图->直观形象、便于理解

2、引入虚拟"头节点"

3、要学会定义辅助节点(比如双向链表的节点插入)

4、快慢双指针(判断链表是否有环、找到环的入口、找链表中倒数第n个节点等)

链表常用操作

1、创建新节点

2、头插(比如逆序链表)

3、尾插

01.两数相加

题目链接:https://leetcode.cn/problems/add-two-numbers/

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例 1:

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

提示:

  • 每个链表中的节点数在范围 [1, 100]
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

思路

这里因为本身就是逆序的链表,其实是方便我们进行计算的,我们只需要一个临时变量来记录进位的值即可,然后我们可以正常按照计算规则逐个相加直至链表结束即可。

/*** 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* cur1=l1, *cur2 =l2;ListNode* newhead=new ListNode();ListNode* prev=newhead;int t=0;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);prev=prev->next;t/=10;}prev=newhead->next;delete newhead;return prev;}
};

02.两两交换链表中的节点

题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1] 

提示:

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

思路

我们可以先创造一个头节点,其次就是画图用原链表和交换后的链表进行对比找规律,利用链表的结点指针来进行交换,找出结束循环的条件即可。

在这里插入图片描述

代码

/*** 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) {if(!head||!head->next) return head;ListNode* newhead=new ListNode();newhead->next=head;ListNode* prev=newhead,*cur=prev->next,*next=cur->next,*nnext=next->next;while(cur&&next){prev->next=next;next->next=cur;cur->next=nnext;prev=cur;cur=nnext;if(cur) next=nnext->next;if(next) nnext=next->next;}prev=newhead->next;delete newhead;return prev;}
};

03.重排链表

题目链接:https://leetcode.cn/problems/reorder-list/

给定一个单链表 L 的头节点 head ,单链表 L 表示为:

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

输入:head = [1,2,3,4]
输出:[1,4,2,3]

示例 2:

输入:head = [1,2,3,4,5]
输出:[1,5,2,4,3] 

提示:

  • 链表的长度范围为 [1, 5 * 104]
  • 1 <= node.val <= 1000

思路

我们画图发现可以先使用快慢指针的方式找到中间节点,然后使用头插法将后半部分逆序,再逐个拼接两段链表即可得到所需要的链表

代码

/*** 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:void reorderList(ListNode* head) {if(!head||!head->next||!head->next->next) return;ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}ListNode* newhead=new ListNode();ListNode* cur=slow->next;slow->next=nullptr;while(cur){ListNode* next=cur->next;cur->next=newhead->next;newhead->next=cur;cur=next;}ListNode* ret=new ListNode();ListNode* prev=ret;ListNode* cur1=head,*cur2=newhead->next;while(cur1){prev->next=cur1;cur1=cur1->next;prev=prev->next;if(cur2){prev->next=cur2;cur2=cur2->next;prev=prev->next;}}delete newhead;delete ret;}
};

04.合并 K 个升序链表

题目链接:https://leetcode.cn/problems/merge-k-sorted-lists/

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4

思路1

这里最简单也是比较高效的一种写法,就是使用一个小根堆,将这k个链表的头节点放进去,逐个将堆顶的最小链表节点拼接,再逐个入堆,最后就可以将k个有序链表完成拼接

代码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 {struct comp{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val>l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,comp> heap;for(auto li:lists) if(li) heap.push(li);ListNode* ret=new ListNode();ListNode* prev=ret;while(!heap.empty()){ListNode* t=heap.top();heap.pop();prev->next=t;prev=t;if(t->next) heap.push(t->next);}prev=ret->next;delete ret;return prev;}
};

思路2

第二种就是使用分治思想中的归并,也可以同样效率完成合并

代码

/*** 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* mergeKLists(vector<ListNode*>& lists) {return merge(lists,0,lists.size()-1);}ListNode* merge(vector<ListNode*>& lists,int left,int right){if(left>right) return nullptr;if(left==right) return lists[left];int mid=(left+right)>>1;ListNode* l1=merge(lists,left,mid);ListNode* l2=merge(lists,mid+1,right);return mergeTlist(l1,l2);}ListNode* mergeTlist(ListNode* l1,ListNode* l2){if(l1==nullptr) return l2;if(l2==nullptr) return l1;ListNode* head=new ListNode();ListNode* cur1=l1,*cur2=l2,*prev=head;head->next=nullptr;while(cur1&&cur2){if(cur1->val<=cur2->val){prev=prev->next=cur1;cur1=cur1->next;}else{prev=prev->next=cur2;cur2=cur2->next;}}if(cur1) prev->next=cur1;if(cur2) prev->next=cur2;return head->next;}
};

05.K个一组翻转链表

题目链接:https://leetcode.cn/problems/reverse-nodes-in-k-group/

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

思路

这里我们可以先计算要翻转的子链表个数,也就是要反转的次数,再使用头插法逐个翻转拼接即可

代码

/*** 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) {int n=0;ListNode* cur=head;while(cur){cur=cur->next;n++;}n/=k;ListNode* newhead=new ListNode();ListNode* prev=newhead;cur=head;for(int i=0;i<n;++i){ListNode* tmp=cur;for(int j=0;j<k;++j){ListNode* next=cur->next;cur->next=prev->next;prev->next=cur;cur=next;}prev=tmp;}prev->next=cur;cur=newhead->next;delete newhead;return cur;}
};

相关文章:

算法沉淀——链表(leetcode真题剖析)

算法沉淀——链表 01.两数相加02.两两交换链表中的节点03.重排链表04.合并 K 个升序链表05.K个一组翻转链表 链表常用技巧 1、画图->直观形象、便于理解 2、引入虚拟"头节点" 3、要学会定义辅助节点&#xff08;比如双向链表的节点插入&#xff09; 4、快慢双指针…...

Flink从入门到实践(一):Flink入门、Flink部署

文章目录 系列文章索引一、快速上手1、导包2、求词频demo&#xff08;1&#xff09;要读取的数据&#xff08;2&#xff09;demo1&#xff1a;批处理&#xff08;离线处理&#xff09;&#xff08;3&#xff09;demo2 - lambda优化&#xff1a;批处理&#xff08;离线处理&…...

python分离字符串 2022年12月青少年电子学会等级考试 中小学生python编程等级考试二级真题答案解析

目录 python分离字符串 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序代码 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python分离字符串 2022年12月 python编程等级考试级编程题 一、题目要…...

Excel练习:折线图突出最大最小值

Excel练习&#xff1a;折线图突出最大最小值 ​​ 要点&#xff1a;NA值在折现图中不会被绘制&#xff0c;看似一条线&#xff0c;实际是三条线。换成0值和""都不行。 ‍ 查看所有已分享Excel文件-阿里云 ‍ 学习的这个视频&#xff1a;Excel折线图&#xff0c…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之MenuItem组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之MenuItem组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、MenuItem组件 用来展示菜单Menu中具体的item菜单项。 子组件 无。 接口 Men…...

Mockito测试框架中的方法详解

这里写目录标题 第一章、模拟对象1.1&#xff09;①mock()方法&#xff1a;1.2&#xff09;②spy()方法&#xff1a; 第二章、模拟对象行为2.1&#xff09;模拟方法调用①when()方法 2.2&#xff09;模拟返回值②thenReturn(要返回的值)③doReturn() 2.3&#xff09;模拟并替换…...

Atcoder ABC339 A - TLD

TLD 时间限制&#xff1a;2s 内存限制&#xff1a;1024MB 【原题地址】 所有图片源自Atcoder&#xff0c;题目译文源自脚本Atcoder Better! 点击此处跳转至原题 【问题描述】 【输入格式】 【输出格式】 【样例1】 【样例输入1】 atcoder.jp【样例输出1】 jp【样例说明…...

企业级DevOps实战

第1章 Zookeeper服务及MQ服务 Zookeeper&#xff08;动物管理员&#xff09;是一个开源的分布式协调服务&#xff0c;目前由Apache进行维护。 MQ概念 MQ&#xff08;消息队列&#xff09;是一种应用程序之间的通信方法&#xff0c;应用程序通过读写出入队列的消息&#xff0…...

C++中的new和delete

1.new和delete的语法 我们知道C语言的内存管理方式是malloc、calloc、realloc和free&#xff0c;而我们的C中除了可以使用这些方式之外还可以选择使用new和delete来进行内存管理。 new和delete的主要语法如下 从上面的代码我们只能知道new要比malloc好写一些&#xff0c;但是其…...

rtt设备io框架面向对象学习-dac设备

目录 1.dac设备基类2.dac设备基类的子类3.初始化/构造流程3.1设备驱动层3.2 设备驱动框架层3.3 设备io管理层 4.总结5.使用 1.dac设备基类 此层处于设备驱动框架层。也是抽象类。 在/ components / drivers / include / drivers 下的dac.h定义了如下dac设备基类 struct rt_da…...

腾讯云幻兽帕鲁服务器配置怎么选择合适?

腾讯云幻兽帕鲁服务器配置怎么选&#xff1f;根据玩家数量选择CPU内存配置&#xff0c;4到8人选择4核16G、10到20人玩家选择8核32G、2到4人选择4核8G、32人选择16核64G配置&#xff0c;腾讯云百科txybk.com来详细说下腾讯云幻兽帕鲁专用服务器CPU内存带宽配置选择方法&#xff…...

796. 子矩阵的和

Problem: 796. 子矩阵的和 文章目录 思路解题方法复杂度Code 思路 这是一个二维前缀和的问题。二维前缀和的主要思想是预处理出一个二维数组&#xff0c;使得每个位置(i, j)上的值表示原数组中从(0, 0)到(i, j)形成的子矩阵中所有元素的和。这样&#xff0c;对于任意的子矩阵(x…...

如何在 Python 中处理 Unicode

介绍 Unicode 是世界上大多数计算机的标准字符编码。它确保文本&#xff08;包括字母、符号、表情符号&#xff0c;甚至控制字符&#xff09;在不同设备、平台和数字文档中显示一致&#xff0c;无论使用的操作系统或软件是什么。它是互联网和计算机行业的重要组成部分&#xf…...

CSDN文章导出PDF整理状况一览

最近CSDN有了导出文章PDF功能&#xff0c;导出的PDF还可以查询&#xff0c; 因此&#xff0c;把文章导出PDF&#xff0c;备份一下自己的重要资料。 目前整理内容如下 No.文章标题整理时间整理之后 文章更新Size &#xff08;M&#xff09;10001_本地电脑-开发相关软件保持位…...

jmeter-05变量(用户定义变量,用户参数,csv文档参数化)

文章目录 一、jmeter有三种变量二、用户定义变量(这个更多的可以理解为全局变量)1、设置2、引用三、用户参数(可以理解为局部变量)1、设置2、引用3、用户参数化要配合线程组的线程数使用4、结果五、csv文档参数1、创建csv文件2、设置2、引用csv文件可以配合线程组的线程数,…...

CSS之水平垂直居中

如何实现一个div的水平垂直居中 <div class"content-wrapper"><div class"content">content</div></div>flex布局 .content-wrapper {width: 400px;height: 400px;background-color: lightskyblue;display: flex;justify-content:…...

2.8日学习打卡----初学RabbitMQ(三)

2.8日学习打卡 一.springboot整合RabbitMQ 之前我们使用原生JAVA操作RabbitMQ较为繁琐&#xff0c;接下来我们使用 SpringBoot整合RabbitMQ&#xff0c;简化代码编写 创建SpringBoot项目&#xff0c;引入RabbitMQ起步依赖 <!-- RabbitMQ起步依赖 --> <dependency&g…...

Unity学习笔记(零基础到就业)|Chapter02:C#基础

Unity学习笔记&#xff08;零基础到就业&#xff09;&#xff5c;Chapter02:C#基础 前言一、复杂数据&#xff08;变量&#xff09;类型part01&#xff1a;枚举数组1.特点2.枚举&#xff08;1&#xff09;基本概念&#xff08;2&#xff09;申明枚举变量&#xff08;3&#xff…...

容器化的基础概念:不可变基础设施解释:将服务器视为乐高积木,而非橡皮泥。

不可变基础设施解释&#xff1a;将服务器视为乐高积木&#xff0c;而非橡皮泥。 想象一下用乐高积木代替橡皮泥进行搭建。使用橡皮泥时&#xff0c;您可以直接塑形和改变它。而使用乐高积木&#xff0c;您需要逐个零件搭建特定结构&#xff0c;并在需要时整体替换它们。这就是…...

智胜未来,新时代IT技术人风口攻略-第二版(弃稿)

文章目录 抛砖引玉 鸿蒙生态小科普焦虑之下 理想要落到实处校园鼎力 鸿蒙发展不可挡培训入场 机构急于吃红利企业布局 鸿蒙应用规划动智胜未来 技术人风口来临 鸿蒙已经成为行业的焦点&#xff0c;未来的发展潜力无限。作为一名程序员兼UP主&#xff0c;我非常荣幸地接受了邀请…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...