算法思想总结:链表
一、链表的常见技巧总结
二、两数相加
. - 力扣(LeetCode)

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//利用t来存进位信息int t=0;ListNode*newhead=new ListNode(0);//创建一个哨兵节点,方便尾插ListNode*ptail=newhead;//ptail方便尾插ListNode* cur1=l1,*cur2=l2;while(cur1||cur2||t==1)//t==1防止后面有进位没加上{if(cur1) {t+=cur1->val; cur1=cur1->next;}if(cur2) {t+=cur2->val;cur2=cur2->next;}ptail->next=new ListNode(t%10);ptail=ptail->next;t/=10;}ListNode*ret=newhead->next;delete newhead;return ret;}
};
三、两两交换链表中的节点

四、重排链表
. - 力扣(LeetCode)

class Solution {
public:void reorderList(ListNode* head) {//方法1,利用一个数据结构将每个节点存起来,通过下标去访问//方法2, (1)利用快慢指针,找中点 (2) 拆开链表 从中点开始往后翻转 (3)进行合并成新链表if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;ListNode*mid=midnode(head);//找到中间节点//断开链表ListNode*l1=head;ListNode*l2=mid->next;mid->next=nullptr;//然后反转2l2=reverseList(l2);//合并链表mergeList(l1,l2);}ListNode*midnode(ListNode* head){ListNode*fast=head;ListNode*slow=head;while(fast->next!=nullptr&&fast->next->next!=nullptr)//确保后面两步能走{fast=fast->next->next;slow=slow->next;}return slow;//此时慢指针指向的就是最小的节点}ListNode* reverseList(ListNode* head){ListNode*p1=nullptr;ListNode*p2=head;ListNode*p3=head->next;//记录下一个要遍历的点while(p2){p2->next=p1;p1=p2;p2=p3;if(p3) p3=p3->next ;}return p1;}void mergeList(ListNode* l1, ListNode* l2){ListNode* temp1,*temp2;while(l1!=nullptr&&l2!=nullptr){temp1=l1->next;temp2=l2->next;l1->next=l2;l1=temp1;//回到原链表0l2->next=l1;l2=temp2;//回到原链表}}
};
五、合并k个升序链表
. - 力扣(LeetCode)

优先级队列:
class Solution {
public://建小堆需要greaterstruct greater //构造一个仿函数{bool operator()(const ListNode*l1,const ListNode*l2){return l1->val>l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {//建立优先级队列(小堆),每次将堆顶元素插入进去,然后再删除堆顶元素,插入下个位置priority_queue<ListNode*,vector<ListNode*>,greater> heap;//建立一个小堆//入堆for(auto l:lists) if(l) heap.push(l);//因为有可能里面存的是一个空链表//开始合并k个有序链表ListNode*newnode=new ListNode(0);ListNode*ptail=newnode;//用于帮助我们进行尾插while(!heap.empty()){//进行尾插ListNode*it=heap.top();ptail->next=it;ptail=it;//去到下一个位置准备尾插//删除堆顶元素并将该节点的下一个节点入堆 ,为空就不入heap.pop();if(it->next) heap.push(it->next);}//此时全部的元素都插入完成了,返回最终的链表ListNode*ret=newnode->next;delete newnode;return ret;//时间复杂度o(n*k*logk)}
};
分治思想:
//策略,利用递归解决问题,结合归并排序,合并两个有序链表 (利用分治思想)
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists){int n=lists.size();return merge(lists,0,n-1);//让merge帮助我们完成整个区间的归并}ListNode* merge(vector<ListNode*>& lists,int left,int right){//首先,处理边界情况,如果不存在链表或者是只有一个链表,此时没有必要进行下去if(left>right) return nullptr;if(left==right) return lists[left];//让merge帮助我们归并左右区间int mid=(left+right)>>1;ListNode*l1=merge(lists,left,mid);ListNode*l2=merge(lists,mid+1,right);//然后开始进行合并两个有序链表return mergetwolist(l1,l2);}ListNode*mergetwolist(ListNode*l1,ListNode*l2){//考虑两个链表为空的情况if(l1==nullptr) return l2;if(l2==nullptr) return l1;//此时两个链表必然不为空,开始进行合并ListNode*newhead=new ListNode(0);//哨兵节点ListNode*ptail=newhead;//帮助我们进行尾插ListNode*cur1=l1,*cur2=l2;//两个指针分别指向两个链表while(cur1&&cur2)//当两个都不为空的时候{if(cur1->val<cur2->val) {//此时要尾插cur1ptail->next=cur1;ptail=cur1;//更新到下一个位置cur1=cur1->next;//继续去下一个节点遍历}else{ptail->next=cur2;ptail=cur2;//更新到下一个位置cur2=cur2->next;//继续去下一个节点遍历}}//可能有的链表没有遍历完if(cur1) ptail->next=cur1;if(cur2) ptail->next=cur2;//此时返回到目标的位置ListNode*ret=newhead->next;delete newhead;return ret;}
};
六、k个一组翻转链表
. - 力扣(LeetCode)

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(0);//创建一个哨兵节点ListNode*prev=newhead;//记住被头插的点cur=head;//从head开始进行头插//翻转n组,每组翻转k个for(int i=0;i<n;++i){ListNode*temp=cur;for(int j=0;j<k;++j){//用头插的逻辑ListNode*next=cur->next;;cur->next=prev->next;prev->next=cur;cur=next;//继续去链表的下一个点}prev=temp;//更新prev}//循环结束后,将后面的不需要逆序的部分接上prev->next=cur;ListNode*ret=newhead->next;delete newhead;return ret;}
};
七、旋转链表
. - 力扣(LeetCode)

思路1:截断再连接
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {//让链表成环(闭合成环),然后在指定位置断开if(head==nullptr||head->next==nullptr||k==0) return head;int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次if(add==count) return head;//避免不需要翻转的情况//截断重连ListNode*cur=head;while(--add) cur=cur->next; //找到被截断的位置ListNode*ret=cur->next;cur->next=nullptr;//断开cur=ret;while(cur->next!=nullptr) cur=cur->next;//找到尾节点cur->next=head;//连接return ret; }
};
思路2:链表成环,指定位置截断
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {//让链表成环,然后在指定位置断开if(head==nullptr||head->next==nullptr||k==0) return head;int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次ptail->next=head;//头尾相连while(add--) ptail=ptail->next;ListNode*ret=ptail->next;ptail->next=nullptr;return ret; }
};
思路3:逆置前n-k个,再逆置后k个,最后整体逆置
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==nullptr||head->next==nullptr||k==0) return head;//先逆置前n-k个,再逆置后k个,再整体逆置int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次if(add==count) return head;//开始找前n-k个节点ListNode*cur=head;while(--add) cur=cur->next;ListNode*l2=cur->next;//第二个链表cur->next=nullptr;//断开ListNode* l1=reverse(head);l2=reverse(l2);head->next=ptail;//连接起来return reverse(l1);//然后整体翻转}ListNode*reverse(ListNode* head){ //只有一个节点,没什么好逆置的if(head==nullptr||head->next==nullptr) return head;ListNode*p1=nullptr,*p2=head,*p3=head->next;while(p2){p2->next=p1;p1=p2;p2=p3;if(p3) p3=p3->next;}return p1;}
};

相关文章:
算法思想总结:链表
一、链表的常见技巧总结 二、两数相加 . - 力扣(LeetCode) class Solution { public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//利用t来存进位信息int t0;ListNode*newheadnew ListNode(0);//创建一个哨兵节点,方便尾插List…...
Android Room 记录一个Update语句不生效的问题解决记录
代码展示 1.数据实体类 Entity public class User {PrimaryKey(autoGenerate true)private long id;private String name;private String age;private String sex;public User(String name, String age, String sex) {this.name name;this.age age;this.sex sex;}public …...
使用SpringBoot3+Vue3开发公寓管理系统
项目介绍 公寓管理系统可以帮助公寓管理员更方便的进行管理房屋。功能包括系统管理、房间管理、租户管理、收租管理、房间家具管理、家具管理、维修管理、维修师傅管理、退房管理。 功能介绍 系统管理 用户管理 对系统管理员进行管理,新增管理员,修改…...
有且仅有的10个常见的排序算法,东西不多,怎么就背不下来呢
就这么跟你说吧,面试中肯定会出排序算法的算法题,你只需要背下来代码背下来他们的时间复杂度和空间复杂度就能蒙混过关。 不管你是前端还是后端,关于排序的算法有且仅有这 10个,如果你用心了,怎么会记不住呢。看完这篇…...
Mac安装配置ElasticSearch和Kibana 8.13.2
系统环境:Mac M1 (MacOS Sonoma 14.3.1) 一、准备 从Elasticsearch:官方分布式搜索和分析引擎 | Elastic上下载ElasticSearch和Kibana 笔者下载的是 elasticsearch-8.13.2-darwin-aarch64.tar.gz kibana-8.13.2-darwin-aarch64.tar.gz 并放置到个人…...
javaWeb项目-快捷酒店管理系统功能介绍
项目关键技术 开发工具:IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7 框架:ssm、Springboot 前端:Vue、ElementUI 关键技术:springboot、SSM、vue、MYSQL、MAVEN 数据库工具:Navicat、SQLyog 1、Spring Boot框架 …...
闲不住,手写一个数据库文档生成工具
shigen坚持更新文章的博客写手,擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长,分享认知,留住感动。 个人IP:shigen 逛博客的时候,发现了一个很有意思的文章:数据库表结构导…...
在群晖上安装GPT4Free
什么是 GPT4Free ? GPT4Free 简称 G4F,是一个强大的大型语言模型命令行界面(LLM-CLI),旨在去中心化并提供免费访问先进人工智能技术的能力。G4F 的目标是通过提供用户友好和高效的工具,使人工智能民主化&am…...
C# 语言类型(四)—传递参数及其修饰符
总目录 C# 语法总目录 参考链接: C#语法系列:C# 语言类型(一)—预定义类型值之数值类型 C#语法系列:C# 语言类型(二)—预定义类型之字符串及字符类型简述 C#语法系列:C# 语言类型(三)—数组/枚举类型/结构体 C#语法系列:C# 语言类型(四)—传递参数及其修饰符 C#语法…...
刷穿力扣006-剑指offer一数组——02寻找目标值-二维数组
刷穿力扣006-剑指offer<一>数组——02寻找目标值-二维数组 基本面试题都是我带大家刷的力扣热题100和剑指offer的75道题,建议刷两遍!(ps:想找工作实习的同学,文末有面试八股和简历模板) 题目: 语言…...
爬虫(小案例)
点开其中一个链接, http://desk.zol.com.cn/dongman/huoyingrenzhe/(前面为浏览器自动补全,在代码里需要自己补全) 可以看到图片的下载地址以及打开本图集下一张图片的链接 了解完网站的图片构造后动手写代码,我们筛…...
环信 IM 客户端将适配鸿蒙 HarmonyOS
自华为推出了自主研发操作系统鸿蒙 HarmonyOS 后,国内许多应用软件开始陆续全面兼容和接入鸿蒙操作系统。环信 IM 客户端计划将全面适配统鸿蒙 HarmonyOS ,助力开发者快速实现社交娱乐、语聊房、在线教育、智能硬件、社交电商、在线金融、线上医疗等广泛…...
伪元素的使用
.box::after{content: ;display: block;// 定义元素位置margin-top: 12rpx;margin-right: 20rpx;// 定义元素宽高width: 36rpx;height: 36rpx;// background-image无法引用本地资源,故需要用网络地址background-image: url($urlcalendar.png);background-size: 100%…...
TensorFlow学习之:高级应用和扩展
生成对抗网络:了解GAN的基本原理,使用TensorFlow实现简单的GAN 生成对抗网络(Generative Adversarial Networks,GAN)由两部分组成:生成器(Generator)和判别器(Discrimin…...
maya模板导入动画
maya模板导入动画,第一帧为模板姿态 要将一个FBX文件中的动画数据导入另一个FBX文件的模板,并使得第一帧是模板的初始姿势,第二帧开始是动画,你可以在Maya中采用以下步骤来操作: 步骤 1: 导入模板FBX 首先ÿ…...
【微信小程序之分包】
微信小程序之分包 什么是分包分包的好处分包前的结构图分包后的结构图分包的加载规则分包的体积限制使用分包打包原则引用原则独立分包独立分包的配置方法独立分包的引用原则分包预下载配置分包的预下载分包预下载限制 什么是分包 分包指的是把一个完整小程序项目,…...
STM32-ADC(独立模式、双重模式)
ADC简介 18个通道:外部信号源就是16个GPIO回。在引脚上直接接模拟信号就行了,不需要侄何额外的电路。引脚就直接能测电压。2个内部信号源是内部温度传感器和内部参考电压。 逐次逼近型ADC: 它是一个独立的8位逐次逼近型ADC芯片,这个ADC0809是…...
03.卸载MySQL
卸载MySQL 1.Windows卸载MySQL8 停止服务 用命令停止或者在服务中停止都可以 net stop mysql(服务名字可以去服务里面看一下)控制面板卸载MySQL 卸载MySQL8.0的程序可以和其他桌面应用程序一样直接在控制面板选择卸载程序,并在程序列表中…...
2024.4.13 蓝桥杯软件类C++B组山东省赛 小记
大三老狗了 , 还是把精力放在考研上了 ,所以只是蓝桥杯的前一晚上把常用算法翻了翻。 其实还做了一场小模拟,两个题分值200分我狂砍了17分,bfs写半小时写不明白,所以晚上已经是心如死灰了,所以就早早睡觉了…...
Windows下IntelliJ IDEA远程连接服务器中Hadoop运行WordCount(详细版)
使用IDEA直接运行Hadoop项目,有两种方式,分别是本地式:本地安装HadoopIDEA;远程式:远程部署Hadoop,本地安装IDEA并连接, 本文介绍第二种。 一、安装配置Hadoop (1)虚拟机伪分布式 见上才艺&a…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...

